排序算法的应用：考查应聘者的抽象建模能力。这道题目要求我们把熟悉的扑克牌转换为数组，把找顺子的过程通过排序、计数等步骤实现。这些都是把生活中的模型用程序语言来表达的例子。

Question

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

测试用例

功能测试（抽出的牌中有一个或者多个大、小王；抽出的牌中没有大、小王；抽出的牌中有对子）。 特殊输入测试（输入 nullptr 指针）。

本题考点

考查应聘者的抽象建模能力。这道题目要求我们把熟悉的扑克牌转换为数组，把找顺子的过程通过排序、计数等步骤实现。这些都是把生活中的模型用程序语言来表达的例子。

Intuition

根据题意，此 \(5\) 张牌是顺子的充分条件如下：

• 除大小王外，所有牌无重复 ；
• 设此 \(5\) 张牌中最大的牌为 \(max\) ，最小的牌为 \(min\) （大小王除外），则需满足：

\[ max - min < 5 \]

因而，可将问题转化为：此 55 张牌是否满足以上两个条件？

集合 + 遍历

算法 遍历五张牌，遇到大小王（即 0 ）直接跳过。 判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 \(O(1)\) ； 获取最大 / 最小的牌： 借助辅助变量 \(max\) 和 \(min\) ，遍历统计即可。

复杂度分析 时间复杂度 \(O(N) = O(5) = O(1)\) ： 其中 \(N\) 为 \(nums\) 长度，本题中 \(N \equiv 5\) ；遍历数组使用 \(O(N)\) 时间。 空间复杂度 \(O(N) = O(5) = O(1)\) ： 用于判重的辅助 Set 使用 \(O(N)\) 额外空间。

排序 + 遍历

算法 先对数组执行排序。 判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 nums[i] = nums[i + 1] 是否成立来判重。 获取最大 / 最小的牌： 排序后，数组末位元素 nums[4] 为最大牌；元素 nums[joker] 为最小牌，其中 joker为大小王的数量。

复杂度分析 时间复杂度 \(O(N \log N) = O(5 \log 5) = O(1)\) ： 其中 \(N\) 为 \(nums\) 长度，本题中 \(N \equiv 5\)；数组排序使用 \(O(N \log N)\)时间。 空间复杂度 \(O(1)\) ： 变量 joker ，使用 \(O(1)\) 大小的额外空间。

参考连接

作者：Krahets 链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

集合 Set + 遍历

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        if not nums:  return False

        # set去重
        res = []
        for num in nums:
            if num == 0:
                continue
            else:
                res.append(num)
        length = len(res)
        res = list(set(res))

        # 判断是否重复
        if len(res) < length:
            return False

        # 判断是否连续
        _min = (1 << 31) - 1
        _max = - (1 << 31)
        for i in res:
            # 更新max和min
            if i > _max:
                _max = i
            if i < _min:
                _min = i
        if _max - _min < 5:
            return True  # 同时满足条件1和条件2
        else:
            return False  # 不满足条件2

排序 + 遍历

# 先对数组执行排序。
# 条件1：不能重复
# 条件2：max - min < 5
class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        # 特判
        if not nums:  return False
        
        # 排序
        nums = sorted(nums)
        length = len(nums)
        
        # 跳过 0
        joker = 0
        while nums[joker] == 0:
            joker += 1
        
        # 检测是否存在重复牌
        for i in range(joker, length):  
            if i + 1 < length and nums[i] == nums[i+1] and nums[i] != 0:
                return False  # 不满足条件1

        # 检测是否连续
        # 排序后，数组末位元素 nums[4] 为最大牌；元素 nums[joker] 为最小牌，其中 joker为大小王的数量。
        if nums[4] - nums[joker] < 5:
            return True  # 同时满足条件1和条件2
        else:
            return False  # 不满足条件2