题目描述

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。

2∼10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，大小王可以看做任意数字。

为了方便，大小王均以 0 来表示，并且假设这副牌中大小王均有两张。

样例

输入：[8,9,10,11,12]

输出：true

算法

(模拟) $O(nlogn)$

1. 先将数组排序
2. 把 0 先过滤掉，找到第一个不为 0 的位置 k
3. 遍历数组，如果有重复元素，肯定不能构成顺子
4. 如果最后一个元素和第一个非 0 元素之差大于 4 nums.back() - nums[k] + 1 > 5 不能构成顺子，否则就是顺子

时间复杂度

数组排序的时间复杂度为 $O(nlogn)$

C++ 代码

class Solution {
public:
    bool isContinuous( vector<int> nums ) {
        if (nums.empty()) return false;

        sort(nums.begin(), nums.end());
        int k = 0;
        while (k < nums.size() && nums[k] == 0) k ++ ;

        for (int i = k + 1; i < nums.size(); i ++ )
            if (nums[i] == nums[i - 1]) 
                return false;

        if (nums.back() - nums[k] + 1 > 5) return false;
        return true;
    }
};