题目链接

牛客网
LeetCode

题目描述

五张牌，其中大小鬼为癞子，牌面为 0。判断这五张牌是否能组成顺子。

61. 顺子 - 图1

解题思路

方法一：set+遍历

我们分两种情况考虑，
一. 如果vector中不包含0的情况：
那么如何判断呢？因为需要是顺子，所以首先不能有重复值， 如果没有重复值，那么形如[1 2 3 4 5]
[5 6 7 8 9]， 会发现最大值与最小值的差值应该小于5.
二. 如果vector中包含0：
发现除去0后的值，判断方法和1中是一样的。
所以根据如上两个条件，算法过程如下：

  1. 初始化一个set，最大值max = 0, 最小值min = 14
  2. 遍历数组， 对于大于0的整数，没有在set中出现，则加入到set中，同时更新max, min
  3. 如果出现在了set中，直接返回false
  4. 数组遍历完，最后再判断一下最大值与最小值的差值是否小于5
  1. class Solution {
  2. public:
  3.     bool IsContinuous( vector<int> numbers ) {
  4.         if(numbers.size() != 5)
  5.             return false;
  6.         set<int> st;
  7.         int max_=0,min_=14;
  8.         for(const int num:numbers){
  9.             if(num>0){
  10.                 if(st.count(num)>0) return false;
  11.                 st.insert(num);
  12.                 max_ = max_ < num ? num : max_;
  13.                 min_ = min_ > num ? num : min_;
  14.             }
  15.         }
  16.         return max_ - min_ < 5;
  17.     }
  18. };
  • 时间复杂度 O(N)
  • 空间复杂度 O(N)

    方法二：排序+遍历

    ```cpp class Solution { public: bool IsContinuous( vector numbers ) {
    1.   if(numbers.size() != 5)
    2.       return false;
    3.   sort(numbers.begin(), numbers.end());
    4.   int zero=0;
    5.   for(int i=0;i<5;i++){
    6.       if(numbers[i]==0){
    7.           zero++;
    8.           continue;
    9.       }
    10.       if(i!=4&&numbers[i]==numbers[i+1]) // 没有重复值
    11.           return false;
    12.   }
    13.   return numbers[4] - numbers[zero] < 5; // 连续的5个数最大差值为4，超过后不会连续
    } };

class Solution { public: bool isStraight(vector& nums) { sort(nums.begin(),nums.end()); int i = 0; while(nums[i]==0){ i++; } for(int j=i+1;j<5;j++){ if(nums[j]==nums[j-1]){ return false; } } return nums[4] - nums[i]<=4; } }; ```

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