剑指Offer题解 - Day36

「剑指 Offer 61. 扑克牌中的顺子」

力扣题目链接[1]

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

「示例 1:」

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

「限制：」

• 数组长度为 5
• 数组的数取值为 [0, 13]

思路：

根据题目要求，我们需要判断长度为5的数组是否是有序的。首先可以得出以下结论：

• 如果数组里面不含大小王，那么获取数组内的最大值max和最小值min，如果max - min < 5 ，准确的说是等于4时，意味着数组有序。
• 如果包含大小王，而题目中说是从若干副扑克牌中抽取，也就意味着可以存在多个0。获取数组内的最大值和最小值，如果max - min < 5 ，意味着数组有序。

那么，现在的重点就在于，找出数组内的极值和判断数组内是否有重复的值(不包括 0)。

Set

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isStraight = function(nums) {
    let max = -Infinity; // 初始化最大值，方便后续更新
    let min = Infinity; // 初始化最小值，方便后续更新
    let set = new Set(); // 初始化集合，存放不重复的值
    for (const item of nums) {
        if (item === 0) continue; // 如果是大小王就跳过
        if (set.has(item)) return false; // 数组元素重复，直接返回
        max = Math.max(max, item); // 更新最大值
        min = Math.min(min, item); // 更新最小值
        set.add(item); // 添加当前元素到集合
    }
    return max - min < 5; // 判断是否满足顺子的条件
};

• 「时间复杂度 O(1)」。
• 「空间复杂度 O(1)」。

分析：

首先我们采用Set来存放不重复的值，通过遍历数组内的元素，判断Set内是否包含当前元素，如果包含则意味着数字重复，直接返回false 。每次遍历都更新最大值和最小值，同时将当前元素添加到集合中。遍历完成后判断max - min < 5 是否成立。

因为大小王可以是任何值，那么遇到0就直接跳过进入下次循环。只要数组中的元素不重复，并且满足max - min < 5 ，就可以说明是顺子。

复杂度方面，由于数组长度只有 5，所以时间复杂度和空间复杂度都是O(1) 。

排序

本题除了使用集合来判重以外，还可以先排序再判断元素是否重复。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const isStraight = (nums) => {
    const arr = nums.concat().sort((a, b) => a - b); // 数组排序
    let notZero = 0; // 初始化非零索引
    for (let i = 0; i < 4; i++) {
        if (arr[i] === 0) { // 如果是0则索引累加，跳过进入下个循环
            notZero++;
            continue;
        }
        if (arr[i] === arr[i + 1]) return false; // 如果元素重复则直接返回false
    }
    return arr[4] - arr[notZero] < 5; // 判断是否为顺子
};

• 「时间复杂度 O(1)」。
• 「空间复杂度 O(1)」。

分析：

首先，将数组拷贝一份然后进行排序，防止影响原数组。然后初始化第一个不是0的索引。

接下来遍历数组，因为要让当前元素和下一个元素进行比较，为了防止元素下表越界，这里的遍历下标的条件是数组长度减一。如果当前元素为 0，对非零索引累加，然后跳过当前循环，进入下个循环。如果当前元素不是零，且与下个元素相同，意味着存在重复元素，则直接返回false 。可以这样判重的前提是数组有序，否则不能直接让当前元素和下一个元素进行判断。

最后取数组最后一个元素和第一个不是0的元素，两者相减，如果值小于5则为顺子。

总结

本题分析了两个解法，使用集合判重，不论数组是否有序都可以。而第二种办法就要确保数组是有序的，才可以通过相邻元素判断是否元素重复。

因为数组的长度只有 5，因此两种方法的时间复杂度和空间复杂度都是O(1) 。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57mpoj/