#JZ45 扑克牌顺子#O(N)和O(NlogN)解法

import java.util.*;
public class Solution {
    //方法一：除了0之外的数中不能有重复，在这基础上最大和最小值的差不能大于5
    //需要保存一个数是否出现过，空间复杂度O(N),时间复杂度O(N)
    public boolean IsContinuous1(int [] numbers) {
        boolean[] isDup = new boolean[14];//0~13
        int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
        for(int num:numbers){
            if(isDup[num]) return false;
            if(num!=0){
                isDup[num] = true;
                max = Math.max(max,num);
                min = Math.min(min,num);
            }
        }
        return max - min<5;
    }
    //方法二:先排好序，然后遍历，有0就记录一下0的数量，然后后面出现断层的时候用上0,0全没了还接不上下一段就返回false
    //时间复杂的O(nlogn),空间复杂度O（1）
    public boolean IsContinuous(int [] numbers) {
        Arrays.sort(numbers);
        int last = -1;
        int zero = 0;
        for(int i = 0;i<numbers.length;i++){
            int num = numbers[i];
            if(num==0){
                zero++;
            }else if(last == -1||num == last + 1){
                last = num;
            }else if(zero!=0){
                last++;
                zero--;
                i--;//还得留下来看看补得齐没有
            }else{
                return false;
            }
        }
        return true;
    }
}