剑指 Offer 61 扑克牌中的顺子

摘要

扑克牌中的顺子

一、集合 Set + 遍历

根据题意，此5张牌是顺子的 充分条件 如下：

• 除大小王外，所有牌 无重复 ；
• 设此5张牌中最大的牌为max，最小的牌为min（大小王除外），则需满足：max−min<5。

因而，可将问题转化为：此5张牌是否满足以上两个条件？

算法步骤：

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

class Solution {public boolean isStraight(int[] nums) {Set<Integer> repeat = new HashSet<>();int max = 0, min = 14;for(int num : nums) {if(num == 0) continue; // 跳过大小王max = Math.max(max, num); // 最大牌min = Math.min(min, num); // 最小牌if(repeat.contains(num)) return false; // 若有重复，提前返回 falserepeat.add(num); // 添加此牌至 Set}return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子}
}

复杂度分析：

• 时间复杂度 O(N)=O(5)=O(1) ： 其中 N为nums长度，本题中N≡5；遍历数组使用O(N)时间。
• 空间复杂度 O(N)=O(5)=O(1)： 用于判重的辅助 Set 使用 O(N) 额外空间

二、排序 + 遍历

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

package Hashmap;import java.util.Arrays;/*** @Classname JZ61扑克牌中的顺子* @Description TODO* @Date 2023/3/7 21:43* @Created by xjl*/
public class JZ61扑克牌中的顺子 {public boolean isStraight(int[] nums) {int joker = 0;Arrays.sort(nums); // 数组排序for(int i = 0; i < 4; i++) {if(nums[i] == 0) {joker++; // 统计大小王数量}else if(nums[i] == nums[i + 1]) {return false; // 若有重复，提前返回 false}}return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子}
}

复杂度分析：

• 时间复杂度 O(Nlog⁡N)=O(5log⁡5)=O(1)： 其中 NN 为nums长度，本题中N≡5；数组排序使用 O(Nlog⁡N)时间。

• 空间复杂度 O(1)： 变量 jokerjoker 使用 O(1)大小的额外空间。

博文参考

《leetcode》