题⽬描述
扑克牌可以组成顺⼦,⼤\⼩ 王可以看成任何数字,并且 A 看作 1 , J 为 11 , Q 为 12 , K 为 13 。 5张牌 【A,0,3,0,5】 就可以变成“ 1,2,3,4,5 ”(⼤⼩王分别看作 2 和 4 ),这样就组成了顺⼦。(可以认为⼤⼩王是 0 。)
输⼊五张牌,如果牌能组成顺⼦就输出true,否则就输出 false 。
示例1 输⼊:[0,3,2,6,4] 返回值:true
思路及解答
排序遍历
这是最直观的解法,通过排序后分析牌之间的间隔关系来判断。
排序后统计大小王数量,检查非王牌之间的间隔是否可用大小王填补:先排序,0肯定是靠左边,然后统计0的个数,后⾯的数,按照第⼀个⾮0的数进⾏递增,如果不是递增,则需要使⽤ 0 牌补充,如果 0 牌不够,需要放回 false,否则直到遍历完数组,返回true 。
时间复杂度:O(n log n),主要来自排序操作
空间复杂度:O(1),只使用常数级别额外空间
哈希集合法(推荐)
利用HashSet实现去重,同时记录最大值和最小值。
初始化⼀个最⼩牌 14,最⼤牌 0,直接使⽤ set 保存数组的元素,如果 set 中已经存在该元素,那么我们直接放回 false,如果 set 中不存在该元素,则将该元素放进 set 中,判断该元素是否⼩于最⼩牌,⼩于则更新最⼩牌,判断该元素是否⼤于最⼤牌,如果⼤于最⼤牌,则更新当前最⼤牌。
为什么 max - min < 5是充分必要条件?
对于5张牌组成的顺子:
如果是连续5张不同数字:max - min = 4
如果有空缺,但能被大小王填补:max - min ≤ 4
如果空缺太大:max - min ≥ 5,即使有4个大小王也无法填补
示例验证:
[1,3,0,0,5]:max=5, min=1, 5-1=4<5 ✓[1,6,0,0,0]:max=6, min=1, 6-1=5≥5 ✗时间复杂度:O(n),只需遍历数组一次
空间复杂度:O(n),HashSet的空间开销
位运算法(空间最优)
利用整数的二进制位来标记牌值是否出现,实现O(1)空间复杂度。
二进制位标记原理:
整数
flag的32位中,用第i位表示数字i是否出现例如:数字3出现 → 将第3位置1:
flag |= 1 << 3检查数字3是否出现:
(flag >> 3) & 1 == 1


时间复杂度:O(n),线性遍历
空间复杂度:O(1),只使用固定数量的整数变量