题解 | #扑克牌顺子#

思路： 题中给出的信息是最多4个零，因此必有一张非零牌，分析顺子两点基本情况：

• 不能有重复的非零牌
• 非零牌之间最大相差为4 若是两张非零牌相差大于4，则需要4张零牌（超出了限制），若是小于等于4，又不重复的情况下，要么零牌补齐，要么本身就是相邻的数字。 故有两种解决方案。

方法一：哈希表 具体做法： 创建一个哈希表，查找重复：遍历数组的同时，遇到非零牌重复，直接不行，若没有重复则加入到哈希表中，等待后续的查找。同时在遍历过程需要记录数组最大值与最小值，最后检查最大值与最小值的差是否大于4.

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        unordered_map<int, int> hash;
        int max = 0, min = 13;
        for(int i = 0; i < numbers.size(); i++){
            if(numbers[i] > 0){
                if(hash.find(numbers[i]) != hash.end()) //顺子不能重复
                    return false;
                else{
                    hash[numbers[i]] = i; //将新牌加入哈希表
                    if(numbers[i] >= max)
                        max = numbers[i];
                    if(numbers[i] <= min)
                        min = numbers[i];
                }
            }
        }
        if((max - min) >= 5)  //如果两张牌大于等于5，身下三张牌无论如何也补不齐
            return false;
        else
            return true;
    }
};

复杂度分析：

• 时间复杂度：O(n)，只遍历了一遍数组
• 空间复杂度：O(n)，创建了哈希表

方法二：排序法 除了哈希表，还有更直观的方法，便是排序后，遍历数组，遇到零牌计数，遇到非零牌计算与其后的间隔数，最后比较零牌数与间隔数，若是间隔数大于零牌数则不能组成顺子。

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        sort(numbers.begin(), numbers.end()); //先排序
        int zero = 0;
        int gap = 0;
        for(int i = 0; i < numbers.size() - 1; i++){ 
            if(numbers[i] == 0) //统计零牌数
                zero++;
            else{
                if(numbers[i + 1] - numbers[i] == 0) //不可重复
                    return false;
                else
                    gap += numbers[i + 1] - numbers[i] - 1; //统计间隔数
            }
        }
        if(gap > zero)
            return false;
        else
            return true;
    }
};

复杂度分析：

• 时间复杂度：O(nlgn)，排序的复杂度
• 空间复杂度：O(1)，没有额外使用空间