面试题61-扑克牌中的顺子_从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这 5 张牌是不是连续的,2～

题目

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

解题思路

我们需要做三件事情：

1.对数组进行排序
2.统计数组中0的个数
3.统计排序之后的数组中相邻数字之间的空缺总数

如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。
最后，我们还需注意一点：如果数组中的非0数字重复出现，则该数组并不是连续的。换成扑克牌的描述方法就是：如果一副牌中含有对子，则不可能是顺子。
由于扑克牌的值出现在0~13之间，我们可以定义一个长度为14的哈希表，这样在O（n）的时间内就能完成排序。

C++实现

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=(int)nums.size(),zeroCount=0,noZeroCount=0;
        for(int i=0;i<n;++i)
        {
            if(nums[i]==0)
                zeroCount++;
            if(i>0&&nums[i-1]!=0&&nums[i]==nums[i-1])
                return false;
            if(i>0&&nums[i-1]!=0&&nums[i]-nums[i-1]>1)
                noZeroCount+=(nums[i]-nums[i-1]-1);
        }        
        return noZeroCount<=zeroCount?true:false; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1. 时间复杂度：O（nlogn），主要为sort排序的时间，时间复杂度略高，但由于本题中数组的长度是固定的，只有5张牌，那么O（n）和O（nlogn）不会有多少区别。
2. 空间复杂度：O（1）