每日一题，提升自己。今天分享一道关于判断扑克牌顺子的题目，且听我细细道来。

数组 - 判断扑克牌顺子

1. 题目描述

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

示例：

示例1:

输入：[1,2,3,4,5]

输出：true

示例2:

输入：[0,0,1,2,5]

输出：true

提示：

1，数组长度为5。

2，数组的数取值为 [0, 13]。

2. 解题思路

        首先我们先来了解一下关于顺子牌的定义。

1. 牌的数量是5张。
2. 牌间的顺序是递增，且差值为1。
3. 牌间不可以有重复数据（大小王除外）。（扑克牌术语：如果一副牌里含有对子，则不可能是顺子）。
4. 大小王可以作为任意牌，即可以作为牌间空隙插入，且数量不限。

2.1 思路一

        首先是对数组进行升序排序。然后遍历数组，统计出0的个数。如果有重复数据就返回false，否则就计算当前数和前一个数的差值减去一，然后用0来抵消两张牌的间隙。当0的个数小于0时，证明大小王的个数不足与补齐牌的间隙，那么就不是顺子。

2.2 思路二

        按照上面的描述，首先我们需要对数组进行升序排序。如果数组中有重复数据，那么就返回false。然后令minVal为不包含大小王的最小值，maxVal为不包含大小王的最大值，由于牌数量为 5，如果是顺子，就一定有maxVal-minVal < 5。否则就不是顺子。

复杂度：

• 时间复杂度：O(NlogN)。
• 空间复杂度：O(1)。

3. 算法流程

3.1 思路一流程

1. 对数组进行从小到大排序。
2. 遍历数组，统计0的个数。当前数大于0时，则0的个数统计完毕，保留当前第一个不为0的数字的角标。
3. 从不为0的部分继续遍历数组，判断当前数与前一个数是否相等。
4. 如果当前数与前一个数相等，返回false；否则0的个数变成当前0的个数减去当前数与前一个数的差再减一。就是看两个数之间需要几个0去补充。
5. 之后判断当0的个数小于0个之后，则返回false。

3.2 思路二流程

1. 对数组进行从小到大排序。
2. 遍历数组，统计0的个数。如果当前不是数组最后一位数，则判断当前数和下一位是否相等，如果相等则直接返回false。
3. minVal是数组中角标为0的个数的数字，maxVal是数组的最后一位数，返回maxVal-minVal < 5的结果。

4. 代码实现

4.1 思路一代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static boolean isStraight(int[] nums){
    Arrays.sort(nums);
    int zero_count = 0;
    int i = 0;
    for (;i<nums.length;i++){
        if (nums[i] > 0){
            break;
        }else if (nums[i] == 0){
            zero_count++;
        }
    }
    for (++i;i<nums.length;i++){
        if (nums[i] == nums[i-1]){
            return false;
        }
        zero_count -= (nums[i] - nums[i-1] - 1);
        if (zero_count < 0){
            return false;
        }
    }
    return true;
}

4.2 思路二代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static boolean isStraight(int[] nums){
    Arrays.sort(nums);
    int zero_count = 0;
    for (int i=0;i<nums.length;i++){
        if (nums[i] == 0){
            zero_count++;
            continue;
        }
        if (i != nums.length-1){
            if (nums[i] == nums[i+1]){
                return false;
            }
        }
    }
    return nums[nums.length-1] - nums[zero_count] < 5;
}