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

Categories:

题目描述
思路分析
1. 解法一：哈希集合（推荐）
2. 解法二：排序 + 遍历
相似题目

题目描述

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

思路分析

解法一：哈希集合（推荐）

核心思路：

大小王（数字 0）可代替任意牌，因此先统计 0 的个数，再判断非零牌。

顺子的两个充分必要条件：① 非零牌中没有重复；② 非零牌的最大值与最小值之差小于 5。

使用哈希集合在遍历过程中同时完成去重检查和 max/min 的维护，一次遍历即可得出结论。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度（固定为 5），遍历一次数组。

空间复杂度：O(n)，哈希集合最多存储 n 个元素。

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0, min = 14;
        for (int num : nums) {
            // 跳过大小王
            if (num == 0) {
                continue;
            }
            // 非零牌有重复，直接返回 false
            if (!set.add(num)) {
                return false;
            }
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        // 最大值与最小值之差小于 5，即可构成顺子
        return max - min < 5;
    }
}

func isStraight(nums []int) bool {
    set := make(map[int]bool)
    max, min := 0, 14
    for _, num := range nums {
        // 跳过大小王
        if num == 0 {
            continue
        }
        // 非零牌有重复，直接返回 false
        if set[num] {
            return false
        }
        set[num] = true
        if num > max {
            max = num
        }
        if num < min {
            min = num
        }
    }
    // 最大值与最小值之差小于 5，即可构成顺子
    return max-min < 5
}

解法二：排序 + 遍历

核心思路：

对数组排序后，所有 0（大小王）会集中在数组头部。

统计 0 的个数（即”万能牌”数量），然后从第一张非零牌开始检查相邻两牌之差。

若相邻牌相等（有重复），直接返回 false；否则累计差值缺口，最终判断缺口是否能被 0 填满。

等价地：排序后只需检查 nums[4] - nums[jokers] < 5（jokers 为 0 的个数）。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度（固定为 5），排序开销。

空间复杂度：O(1)，仅使用常数级额外空间。

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int jokers = 0;
        for (int i = 0; i < 4; i++) {
            // 统计大小王数量
            if (nums[i] == 0) {
                jokers++;
                continue;
            }
            // 相邻非零牌相等，说明有重复
            if (nums[i] == nums[i + 1]) {
                return false;
            }
        }
        // 最大牌与最小非零牌之差小于 5，即可构成顺子
        return nums[4] - nums[jokers] < 5;
    }
}

func isStraight(nums []int) bool {
    sort.Ints(nums)
    jokers := 0
    for i := 0; i < 4; i++ {
        // 统计大小王数量
        if nums[i] == 0 {
            jokers++
            continue
        }
        // 相邻非零牌相等，说明有重复
        if nums[i] == nums[i+1] {
            return false
        }
    }
    // 最大牌与最小非零牌之差小于 5，即可构成顺子
    return nums[4]-nums[jokers] < 5
}

相似题目

题目	难度	考察点
268. 丢失的数字	简单	数学 / 哈希表
剑指 Offer 03. 数组中重复的数字	简单	哈希表 / 原地交换
442. 数组中重复的数据	中等	原地哈希
645. 错误的集合	简单	哈希表 / 数组标记
128. 最长连续序列	中等	哈希集合
41. 缺失的第一个正数	困难	原地哈希

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/66178625