解法一:排序

在解决此题目之前,需要明确:在达到何种要求时,会实现「顺子」。

显而易见,当所抽取的非零牌存在重复时,不可能有顺子出现;此外,由于0可以代替任意牌,因此能否组成顺子是由「非零牌」决定的。故,此题的本质是要我们寻找非零牌之间是否满足一定的关系。

题目说明每次抽取牌的数量为5,因此若非零牌中的最大值与最小值之差小于5,则一定会组成顺子

因此,题目转变成为:在非零牌中,寻找最大牌与最小牌,并计算其距离是否小于5。

解法一的思路如下:

  1. 将原数组排序(可利用C++内置的sort()方法进行排序);
  2. 可以得到数组中的最大数max(即有序数组的最后一个元素);
  3. 从头开始遍历排序好的数组:
    1. 若遇到0,跳过;
    2. 若遇到重复元素,返回false;
    3. 若max与当前值之差大于4,返回false;
  4. 循环结束时,比满足「最大值与最小值之差小于等于4」、「不存在重复元素」,因此直接返回true。

代码实现如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (!numbers.size())
            return false;
        sort(numbers.begin(), numbers.end());  // 排序
        int i = 0, max_ = numbers[numbers.size() - 1]; // 最大值为数组的最后一个元素
        // 遍历数组
        while (i < numbers.size() - 1) {
            // 跳过0
            if (!numbers[i]) {
                i++; 
                continue;
            }
            // 若有重复,返回false
            if (numbers[i] == numbers[i + 1]) 
                return false;
            // 若最大与最小之差大于4,返回false
            if (max_ - numbers[i] > 4) 
                return false;
            i++;
        } 
        return true;
    }
};

排序算法的平均时间复杂度为O(NlogN),遍历数组时间复杂度为O(N),因此总时间复杂度为O(NlogN)。

该方法未定义额外空间,空间复杂度为O(1)。

解法二:哈希表

可以优化上述方法的时间复杂度至O(N),即不采用排序算法。

如上文所述,题目转变成为:在非零牌中,寻找最大牌与最小牌,并计算其距离是否小于5。

因此,通过遍历原数组,并找出其最大值、最小值,即可解决此问题:预先定义变量min、max,分别代表最小值、最大值,并在遍历数组的过程中更新其取值,即可找到整个数组的最大、最小值(非0)。

此题需要注意重复元素的情况,因此引入哈希表便于判断:对于每一个遍历到的元素,在哈希表中进行寻找,若找到,说明有重复,否则将其加入哈希表中。

事例1:
图片说明

事例2:
图片说明

代码如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        int max_ = -1, min_ = 14;
        unordered_map<int, int> hash; // 定义哈希表
        for (int i = 0; i < numbers.size(); i++) {
            if (numbers[i]) { // 跳过0
                if (hash.find(numbers[i]) != hash.end()) // 若在哈希表中找到,说明有重复
                    return false;
                hash[numbers[i]] = 1; // 未在哈希表中找到,将其加入哈希表继续遍历
                max_ = max(max_, numbers[i]); // 最大值
                min_ = min(min_, numbers[i]); // 最小值
            }
        }
        if (max_ - min_ <= 4)
            return true;
        return false;
    }
};

此方法仅遍历数组一次,且哈希表的查找复杂度为O(1),故总时间复杂度为O(N);此方法定义了哈希表用来存储元素,因此空间复杂度为O(N)。