剑指61：扑克牌中的顺子

传送门

nowcoder
leetcode

题目描述

五张牌，其中大小王可以看作任意牌，牌面为 0。
现在有2副扑克牌，从扑克牌中随机五张扑克牌，判断是不是顺子。

C++ 代码 - nowcoder

/*
    数组排序，然后计算所有相邻数字间隔总数。
    统计 0 的个数，
        如果大于等于数字间隔总数，则是顺子；
        否则，不是顺子。

    时间复杂度：O(1)
    	O(nlogn) = O(5log5) = O(1)
    空间复杂度：O(1)
*/
class Solution {
public:
    bool IsContinuous(vector<int>& nums) {
        int n = nums.size();
        if (n < 5) return false;

        int zeroCount = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i ++) {
            if (nums[i] == 0) zeroCount ++;
        }

        for (int i = zeroCount; i < n - 1; i ++) {
            if (nums[i] == nums[i + 1]) return false;
            else {
                int distance = nums[i + 1] - nums[i] - 1;
                zeroCount -= distance;
                if (zeroCount < 0) return false;
            }
        }

        return zeroCount >= 0;
    }
};

C++ 代码 - leetcode

/*
	不需要排序，遍历 nums 数组找最大值和最小值，然后用一个集合判断重复元素。
	
	计算 5 个元素中的最大值和最小值，判断是否递增。
	最大值和最小值的差小于 5，说明是 5 个递增的元素。
	0 不参与最大最小值的选取，不出现重复元素。
	
	时间复杂度：O(1)
		O(n) = O(5) = O(1)
	空间复杂度：O(1)
		O(n) = O(5) = O(1)
*/
class Solution {
public:
    bool checkDynasty(vector<int>& nums) {
        unordered_set<int> set;
        int maxValue = 0, minValue = 14;
        for(int num : nums) {
            if(num == 0) continue; // 跳过元素 0
            if(set.find(num) != set.end()) return false; // 若有重复元素，则提前返回 false

            set.insert(num);
            maxValue = max(maxValue, num);
            minValue = min(minValue, num);
        }

        return maxValue - minValue < 5; // 最大值 - 最小值 < 5，则连续
    }
};