题目描述

image.png

解题思路

本题最重要思路：就是判断什么时候是顺子。
根据题意，此 55 张牌是顺子的 充分条件 如下：
除大小王外，所有牌 无重复 ；
设此 5 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：max - min < 5
因此可将问题转化为：此 5 张牌是否满足以上两个条件？
5张牌中有2个鬼，三张牌有数字，就算不连在一起，那么2张鬼也可以随意充当，也满足max−min<5就是顺子。
利用这个思路可以使用哈希表或者排序法。

哈希表

  • 遍历五张牌，遇到大小王（即 0 ）直接跳过。
  • 判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1) ；
  • 获取最大 / 最小的牌： 借助辅助变量 ma 和 mi ，遍历统计即可。

复杂度分析：

  • 时间复杂度 O(1) ： 本题中给定牌数量 N≡5 ；遍历数组使用 O(N)=O(5)=O(1) 时间。
  • 空间复杂度 O(1) ： 用于判重的辅助 Set 使用 O(N) = O(1)4 额外空间。
  1.     /**
  2.         * 哈希表
  3.         *
  4.         * @param nums
  5.         * @return
  6.         */
  7.     public boolean isStraight(int[] nums) {
  8.         // 0直接跳过，找出最大值和最小值
  9.         int max = 0, min = Integer.MAX_VALUE;
  10.         HashSet<Integer> set = new HashSet<>();
  11.         for (int num : nums) {
  12.             if (num == 0) continue;
  13.             max = Math.max(num, max);
  14.             min = Math.min(num, min);
  15.             if (set.contains(num)) return false;
  16.             set.add(num);
  17.         }
  18.         return max - min < 5 ? true : false;
  19.     }

排序 + 遍历

  • 先对数组执行排序。
  • 判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 nums[i] = nums[i + 1] 是否成立来判重。
  • 获取最大 / 最小的牌： 排序后，数组末位元素 nums[4] 为最大牌；元素 nums[joker] 为最小牌，其中 joker 为大小王的数量。

复杂度分析：

  • 时间复杂度 O(1) ： 本题中给定牌数量 N≡5 ；数组排序使用 O(NlogN)=O(5log5)=O(1) 时间。
  • 空间复杂度 O(1) ： 变量 joker 使用 O(1) 大小的额外空间。
    1. /**
    2.       * 排序
    3.       *
    4.       * @param nums
    5.       * @return
    6.       */
    7.   public boolean isStraight(int[] nums) {
    8.       Arrays.sort(nums);  // 可以自己写快排
    9.       // 大王在前面
    10.       int count = 0;  // 大王的数量
    11.       for (int i = 0; i < 4; i++) {
    12.           if (nums[i] == 0) {
    13.               count++;   // 大王的数量加一
    14.               continue;
    15.           }
    16.           if (nums[i] == nums[i + 1]) return false; // 如果后面有重复
    17.       }
    18.       return nums[nums.length - 1] - nums[count] < 5 ? true : false;
    19.   }