题⽬描述

扑克牌可以组成顺⼦,⼤\⼩ 王可以看成任何数字,并且 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 &lt;&lt; 3

  • 检查数字3是否出现:(flag &gt;&gt; 3) & 1 == 1

  • 时间复杂度:O(n),线性遍历

  • 空间复杂度:O(1),只使用固定数量的整数变量