当前位置：首页 > news >正文

剑指 Offer 61 扑克牌中的顺子

news 2025/7/1 9:50:32

摘要

扑克牌中的顺子

一、集合 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 则可构成顺子}
}

复杂度分析：