剑指 Offer 61. 扑克牌中的顺子

解题思路：排序 + 遍历

本题给定的描述并不明确，我们抽出的 5 张牌应该是从多副扑克混合后抽取的 5 张牌；所以，可能有多张重复的元素，也有可能出现：[0，0，0，0，0] 这样的情况。

如何判断我们拿到的是“顺子”？

将手中的牌从小到大进行排序

  • 除去大小王外，所有的牌均不重复。

  • 刨去大小王，牌与牌之间的差值和不超过 4 即满足“顺子”的条件。

示例：

[0，0，1，4，5]

对于上述示例，首先，除去大小王，所有的牌不重复；刨去大小王，牌与牌之间的差值和为 (4-1) + (5-4) ≤ 4

所以，我们抽到的这 5 张牌满足“顺子”条件。

代码

  1. class Solution {
  2.     public boolean isStraight(int[] nums) {
  3.         Arrays.sort(nums);
  4.         int i = 0;
  5.         while(nums[i] == 0){
  6.             i++;
  7.         }
  8.         int count = 0;
  9.         for(; i < nums.length - 1; i++){
  10.             if(nums[i] == nums[i + 1]){
  11.                 return false;
  12.             }
  13.             count += nums[i + 1] - nums[i];
  14.             if(count > 4){
  15.                 return false;
  16.             }
  17.         }
  18.         return true;
  19.     }
  20. }

复杂度分析

  • 时间复杂度：O(N * logN)

本解法涉及到对数组排序，所以时间复杂度为 O(N * logN)

  • 空间复杂度：O(1)

我们只使用了有限的几个变量，所以额外空间占用 O(1)