【LeetCode】剑指 Offer 61. 扑克牌中的顺子 p298 -- Java Version

题目链接：https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

1. 题目介绍（61. 扑克牌中的顺子）

从若干副扑克牌中随机抽 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

【条件约束】：

限制：

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

2. 题解

2.1 排序 + 遍历 – O(nlogn)

时间复杂度O(nlogn)，空间复杂度O(1)

【解题思路】：
阅读该题示例，我们就能很容易的发现该题和真实世界中的扑克牌顺子还是有所区别的，区别在于：A 与 2 是作为数字 1 与 2 来和 3、4、5组成顺子，而不是真实世界中与 J、Q、K组成顺子，且 大小王可以作为万能牌 来代替其它任意数字，也正是因为这点区别，反而降低了题目的难度。
……
明白了以上思路，我们只需要做 3 件事情即可解题：

1. 首先把数组排序（即 单调递增）；
2. 其次统计数组中 0 的个数（即 万能牌的个数）；
3. 最后统计排序之后的数组中相邻数字之间的空缺总数，如果空缺的总数小于或等于 0 的个数，说明数组连续，否则数组则不连续。

……
【实现策略】：
根据以上分析，我们很容易就能得到编程思路：

1. 首先进行无效输入判断；
2. 使用库函数 sort() 对数组进行排序，该排序的时间复杂度为 O(nlogn)；
3. 遍历数组，统计数组中 0 的个数；
4. 统计数组中达成顺子空缺的间隔数
5. 对比空缺数与0的个数，如果空缺>0的个数，说明不是顺子。

class Solution {
    // Solution 1.1：排序 + 遍历
    // 1. 对数组进行排序
    // 2. 统计数组中0的个数
    // 3. 统计数组中达成顺子空缺的间隔数
    public boolean isStraight(int[] nums) {
        // 无效输入判断
        if (nums.length <= 0) return false;
        // 对数组进行排序
        Arrays.sort(nums);

        int arraysZeroNum = 0;
        int arraysGapNum = 0;

        // 遍历数组，统计数组中0的个数
        for (int i = 0; i < nums.length; i++) {
            // 因为数组已经经过排序，所以遇到不为0的数时，可以直接结束循环
            if (nums[i] != 0) break;
            arraysZeroNum++;
        }

        // 统计数组中达成顺子空缺的间隔数
        int small = arraysZeroNum;  // 第一个不为0的元素的下标
        int big = small + 1;
        while (big < nums.length) {
            // 出现重复数字，一定不是顺子
            if (nums[small] == nums[big]) return false;

            // 排序是单调递增，因此后面的数都比前面的要大
            arraysGapNum += nums[big] - nums[small] - 1;
            small = big;
            big++;
        }

        // 对比空缺数与0的个数，如果空缺>0的个数，说明不是顺子
        return (arraysGapNum > arraysZeroNum) ? false : true;
    }
}

【代码简化：】：
Solution 1.2 为对 Solution 1.1的代码简化，具体简化如下：

1. 将判重与统计万能牌的遍历合并在了一起；
2. 省略了 Solution 1.1 中对数组中顺子空缺数的统计，转而使用 最大牌 - 最小牌 < 5 这一条件表达式代替，极大的简化了代码。

class Solution {
    // Solution 1.2：排序 + 遍历 简化版
    // 简化：将逐一计算数字中数字的空缺数改为直接用 最大牌 - 最小牌 < 5 的方式
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

3. 参考资料

[1] 面试题61. 扑克牌中的顺子（集合 Set / 排序，清晰图解）