剑指offer63_扑克牌的顺子

扑克牌的顺子

---

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

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

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

注意，有可能手里没有拿任何牌。

样例1

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

样例2

输入：[0,8,9,11,12]输出：true

---

算法思路

算法步骤如下：

1. 首先检查输入是否为空，如果是则直接返回false
2. 对数组进行排序，这样可以把所有的0（大小王）放在前面
3. 统计0的个数k
4. 检查非零部分是否有重复数字，如果有则不能组成顺子
5. 检查最大的非零数字与最小的非零数字之差是否≤4（因为有k个0可以填补空缺）

• 时间复杂度：O(nlogn)，主要来自排序操作
• 空间复杂度：O(1)，只使用了常数个额外变量

class Solution {
public:bool isContinuous(vector<int> nums) {// 处理空输入情况if(nums.empty()) return false;// 排序数组，0会被排在最前面sort(nums.begin(), nums.end());// 统计0的个数int k = 0;while(k < nums.size() && !nums[k]) k++;// 检查非零部分是否有重复for(int i = k + 1; i < nums.size(); i++) {if(nums[i] == nums[i - 1]) {return false;}}// 检查最大值和最小值的差是否≤4// 因为有k个0可以填补空缺，所以只要nums.back()-nums[k]≤4就能组成顺子return nums.back() - nums[k] <= 4;}
};

---

实例演示

样例1: 有效顺子
输入: [1,2,3,4,5]

1. 排序后: [1,2,3,4,5]
2. k=0 (没有0)
3. 没有重复数字
4. 5-1=4 ≤4 → 返回true

样例2: 有大小王的顺子
输入: [0,0,1,2,5]

1. 排序后: [0,0,1,2,5]
2. k=2 (两个0)
3. 没有重复数字
4. 5-1=4 ≤4 → 返回true (两个0可以当作3和4)

样例3: 有重复数字
输入: [0,1,2,2,4]

1. 排序后: [0,1,2,2,4]
2. k=1 (一个0)
3. 发现重复数字2 → 返回false

样例4: 差值过大
输入: [0,1,2,3,6]

1. 排序后: [0,1,2,3,6]
2. k=1 (一个0)
3. 没有重复数字
4. 6-1=5 >4 → 返回false