LeetCode 1394 幸运数：计数数组与频率统计的高效解法

1. 幸运数到底在找什么：先把定义嚼碎

1.1 官方定义与示例拆解

LeetCode 1394 Find Lucky Integer in an Array，中文题名叫“找出数组中的幸运数”。题目给一个整数数组 arr，要求返回数组中的最大幸运整数。那什么数字才叫“幸运”？定义一句话：如果一个整数 x 出现在数组中的次数恰好等于 x 本身，那么 x 就是一个幸运整数。

这句话有点像绕口令，我第一次刷到时也愣了几秒。后来我习惯把它翻译成大白话：数字自己是几，它在数组里就必须正好出现几次，两边相等才算数。比如数字 3 出现了 3 次，3 就是幸运的；数字 3 如果只出现 2 次，那它就不是幸运的，因为次数 2 不等于数值 3。

拿官方的例子过一遍。arr = [1, 2, 2, 3, 3, 3]：

• 数字 1 出现 1 次，1 等于 1，幸运。
• 数字 2 出现 2 次，2 等于 2，幸运。
• 数字 3 出现 3 次，3 等于 3，幸运。

三个数字全是幸运数，但题目说了要“最大的幸运整数”，所以答案取 3，不是 1 也不是 2。

再看另一个例子 arr = [2, 2, 3, 4]：

• 2 出现 2 次，等于自身，幸运。
• 3 出现 1 次，1 不等于 3，不幸运。
• 4 出现 1 次，1 不等于 4，不幸运。

最后返回 2。

1.2 容易被忽略的“最大”和“不存在”两个细节

这题有两个细节，特别容易让第一次提交的人吃 WA。第一个就是“最大”，前面已经提到了。很多刚上手的朋友看到“幸运”两个字，脑子里只想着“找到一个符合条件的就返回”，于是拿哈希表统计完后正序遍历，碰到第一个 value == key 就直接返回，这在 [1, 2, 2, 3, 3, 3] 上就会错返回 1，而正确是 3。

第二个细节是“没有幸运数时要返回 -1”。别小看这个哨兵值。数组里可能出现一个数字出现了很多次，但次数永远对不上数值；也可能所有数字都只出现一次，而它们本身又都不是 1，那整个数组就没有一个幸运数。这时候返回 -1 是硬性要求。有人习惯把结果变量初始化为 0，循环结束发现没更新就直接返回 0，可惜题目取值范围是 1 到 500，0 根本不会被当作合法答案，这样写的返回值会被判错。

我在带新人时经常说一句话：这种“建表 + 二次扫描”的题，核心动作其实只有两个，第一遍统计频率，第二遍按需求筛选。难点从来不在统计本身，而在筛选阶段要考虑清楚“要不要取最大”“找不到怎么办”“遍历顺序是升还是降”。想通了这些，代码写起来就是十分钟的事情。

2. 暴力求解的推演：能跑通，但这道题不该这么做

2.1 逐个数检查频率的直观方案

最朴素的解法不需要任何数据结构知识，沾到题目就能写。思路是这样的：把数组里的每个不同数字拿出来，再从头到尾重新数一遍这个数字出现了几次，数出来的次数如果恰好等于这个数字本身，就把它当成候选幸运数；最后在所有候选里挑最大的返回。

写成伪代码大概是这样：

code复制for each 数组中的不同数字 v:
    count = 0
    for each 数组元素 x:
        if x == v:
            count = count + 1
    if count == v:
        best = max(best, v)

return best 存在 ? best : -1

这个方案是百分之百正确的，因为它就是把题目描述机械翻译成代码，没有任何跳过逻辑。放在 arr 长度只有 500、数字范围只有 1 到 500 的环境里，它甚至能直接通过 LeetCode 的测试用例。我建议所有刚开始刷题的人都先写一遍这种暴力版本，不是为了提交上去炫耀，而是为了建立“先有正确答案，再谈优化空间”的做题顺序。一个人如果连暴力都写不出来，那直接写优化版本常常是空中楼阁。

2.2 暴力背后的复杂度账本

但为什么说这不是这道题该用的解法？我们把账算清楚。外层要遍历“数组里的不同数字”，最坏情况下数组里的 500 个数字全部不同，外层就有 500 次循环；内层每次都要把整个数组从头扫到尾，又是 500 次。两层相乘，总比较次数大约是 500 × 500 = 25 万次。25 万次比较对 CPU 来说几乎是零成本，所以它能够 AC。

可问题在于，这种“能 AC”是很脆弱的。同样的代码逻辑，如果把 n 放大到 10 万，10 万的平方就是 100 亿次操作，再快的计算机也要跑好几秒，评测机直接给你一个超时。所以每次准备用暴力解法的时候，我都建议在心里先给自己提个醒：我是不是在用题目给的小数据范围掩盖算法上的偷懒？面试官想听的，往往不是“你能跑通”，而是“你知道哪里能优化、为什么优化”。

顺带一提，也有人会提出排序后再扫描：先把数组排序，然后把连续相同的数字分成一段一段，再看每一段的长度是否等于这段数字本身。这个方案的时间复杂度是 O(n log n)，比暴力 O(n^2) 好，但依然不如计数数组的 O(n)。而且排序会丢失原数组顺序，在这道题里虽然不影响结果，但属于绕远路。正确工具就在手边，没必要先跑去排序。

3. 为什么计数数组是正解：一道题背后的选择逻辑

3.1 数据范围是突破口：arr[i] 被限制在 1~500

这道题真正藏着的钥匙，是约束条件里的这句话：1 <= arr[i] <= 500。它说明数组元素最大值不会超过 500，最小值不会小于 1，不会出现负数，也不会出现 0。那我就可以开一个长度 501 的整数数组 cnt，用“数组下标”来表示“数字本身”，用“数组的值”来表示“这个数字在 arr 里出现了多少次”。

这个设计的精妙之处在于，它把“查找”变成了一次 O(1) 的下标索引。统计阶段，我遍历一遍 arr，看到数字 x 就执行一次 cnt[x]++，就像往统计表里画正字；筛选阶段，我遍历一遍 cnt，找到第一个满足 cnt[i] == i 的下标 i，这就是答案。

为什么数组长度是 501 而不是 500？因为下标要从 0 到 500 全覆盖，而 500 这个值是合法输入，需要 cnt[500] 这个位置来存它的出现次数。如果只开 int[500]，下标范围是 0 到 499，一旦输入里出现 500，程序直接抛数组越界异常。这是新手最常踩的坑之一，我后面还会专门再提。

3.2 HashMap 与数组的取舍

提到“统计频率”，大部分人第一反应是哈希表。在这个场景里，HashMap 确实是完全正确且通用的选择，代码也很简单：

java复制Map<Integer, Integer> map = new HashMap<>();
for (int x : arr) {
    map.put(x, map.getOrDefault(x, 0) + 1);
}

然后遍历 map 的 entry，判断 value == key，取最大的 key 返回。这套流程在数值范围很大、或数值类型不连续的题目里是标准解法，没有任何问题。但它放在这道题里，多少有点高射炮打蚊子。

原因有三点。

第一，空间开销。HashMap 要存储键值对，每个 Integer 都会被装箱，还要维护哈希桶和节点对象。而固定数组只占 501 个 int，大概是 501 × 4 字节 = 2004 字节，也就是 2KB 左右，小到可以整个塞进 CPU 缓存。第二，时间常数。HashMap 的每次 put 和 get 都要计算哈希、定位桶、处理可能的冲突和扩容，虽然均摊复杂度是 O(1)，但常数因子比数组下标访问大得多。第三，代码可读性。数组版本的循环就三行，面试时你可以随口说出“用值域直接映射下标”，比解释“为什么这个 key 的 value 要等于 key”更容易让人听懂。

为了不产生误会，我特别说明：这里不是在否定 HashMap，而是强调工程上的工具选择要匹配场景。看到“整数”、看到“范围小”、看到“连续”，就应该条件反射切换到计数数组。这个反射弧越短，你刷题和面试的表现越稳定。

3.3 完整代码与关键注释

以 Java 为例，完整的可提交代码如下：

java复制class Solution {
    public int findLucky(int[] arr) {
        int[] cnt = new int[501];
        for (int x : arr) {
            cnt[x]++;
        }
        for (int i = 500; i >= 1; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

代码就两个循环，但两个循环的细节都值得琢磨。第一个循环统计频次，没有任何特别之处，重点在数组大小。第二个循环从 500 往 1 倒着扫，而不是从 1 往 500 正着扫。为什么要倒着扫？因为题目要“最大”的幸运数，倒着扫第一个命中的下标天然就是最大值，不需要额外维护一个 best 变量；如果正着扫，你碰到第一个符合条件的数字时还不能确定它就是最大的，必须继续把整个数组扫完，要么多存一个最大值，要么就得记录到底有没有命中。

至于最后那个 return -1，它是所有路径都走完、没有任何命中时的兜底，Java 编译器要求必须有返回值，没有这行代码连编译都过不去。逻辑上它也对应用户返回 -1 的要求。

4. 实测提交与耗时 100 的真相

4.1 提交记录里那个“100ms”怎么看

“耗时 100”这类字眼经常出现在标题或提交记录里。如果真按 LeetCode 页面显示的运行时间看，100ms 对于这道题是一个不需要紧张的数值。LeetCode 的耗时统计本身波动极大，同一个代码，同一台电脑，隔几分钟重交一次，可能一次 80ms、一次 120ms。原因是评测机的 CPU 负载、网络延迟、语言运行时状态、并发提交数量都会影响最终显示。它本质上是一个很粗糙的参考指标，不是基准测试报告。

所以看到 100ms 先别慌，更别急着去“优化”。真正应该关心的是复杂度有没有问题。这道题已经做到 O(n) + O(500) 的扫描，理论上限就摆在那里，你再怎么优化也无法在复杂度上突破；至于常数层面的优化，在这道题的数据规模下毫无意义。LeetCode 的测试数据长度最多 500，哪怕你把代码写得再烂，只要算法是线性的，运行时间都在个位数毫秒到一百毫秒这个区间里浮动，区别大多来自评测环境，而不是你写得好不好。

4.2 从 500 倒着找：一个让代码少跑半程的小优化

前面提过倒序扫描，这里再展开一点。倒着扫描实质上是把“寻找最大满足条件的下标”和“提前终止”合到了一起。你从允许的最大值 500 开始，一路往下检查，第一个 cnt[i] == i 就是答案，因为比 i 更大的数字都已经检查过了，不可能再出现更大的幸运数。命中后直接 return，循环结束，函数退出，连后面的扫描都不用做。

如果是正序扫描，要么需要把所有满足条件的值都走一遍，用额外变量记录最大值；要么拿到第一个满足条件的就贸然返回，结果在 [1, 2, 2, 3, 3, 3] 这种用例上返回 1 而不是 3。使用倒序设计就没有这个纠结：方向本身承载了“取最大”的逻辑，代码量少，还不用担心顺序坑。我遇到需求是“最大/最小”的题，都会条件反射地选择从边界值反向扫描，这是一个非常实用的做题习惯。

4.3 多语言对照实现

这道题的解法在主流语言里几乎可以逐行平移。Python 版本：

python复制class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = [0] * 501
        for x in arr:
            cnt[x] += 1
        for i in range(500, 0, -1):
            if cnt[i] == i:
                return i
        return -1

C++ 版本：

cpp复制class Solution {
public:
    int findLucky(vector<int>& arr) {
        int cnt[501] = {0};
        for (int x : arr) cnt[x]++;
        for (int i = 500; i >= 1; i--) {
            if (cnt[i] == i) return i;
        }
        return -1;
    }
};

语言之间的差别只在声明语法和数组初始化方式，算法骨架三行完全一致。这也是为什么我建议把这类题目在两种语言里各写一遍：你会直观地感受到，算法思想一旦清晰，切换语言只是翻译语法的过程，而不是重新思考解题逻辑。

5. 边界用例与翻车现场：细节决定一次 AC 还是 WA

5.1 最容易踩的三个坑

题是好题，但越简单的题越容易在小河沟里翻船。我自己总结出三个高频错误，每一个都能写成一次 WA 血泪史。

坑一，计数数组长度开不足。有人写 int[500]，看起来“范围是 1 到 500，开 500 个正正好”，结果输入里只要出现一个 500，程序就数组越界。正确长度是 max_value + 1，因为下标从 0 开始计数。这个坑尤其隐蔽，因为大多数测试用例里不会出现最大值 500，你要等到一个边界用例才知道自己错了。养成习惯：看到“数值范围 1 到 N”，直接开 N + 1。

坑二，判断条件写成 cnt[i] >= i。如果数组是 [1, 1, 1, 1]，数字 1 出现了 4 次，4 >= 1 成立，程序会错误地认为 1 是幸运数。但题目要求“恰好出现”，是严格相等，不是“至少”。这种错往往不是不会做，而是把业务语言里的“达到标准”惯性带进了代码里。凡遇到“恰好”“等于”“刚刚好”这类词，翻译成代码时一定要用 ==。

坑三，没有处理找不到幸运数的兜底。Java 里缺 return -1 会直接编译报错，报错其实还算好，至少你立刻就知道有问题；Python 或 C++ 里如果缺兜底，可能返回一个不可预期的值，甚至顺延执行到函数末尾返回空值，这种错误反而更难排查。所以兜底不是可有可无，它是正确性的一部分。

5.2 一组可以直接粘贴的测试用例

每次提交前，我喜欢先用一组覆盖边界的用例做本地验证。以下用例如果你全跑通了，基本可以放心提交：

这些用例设计不是拍脑袋。前几个覆盖“单元素”“没有幸运数”“多幸运数取最大”，后两个特意打向数组边界和数值上限。跑完这一轮，你踩的坑基本都能暴露出来。

6. 从 1394 扩展出去：频率统计类题目的通用套路

6.1 见到“小范围数值”就该有的反射

做完 1394 之后，我建议你在脑子里固化一个反射：当题目告诉你数值范围很小（比如 1 到 500、0 到 100、a 到 z），优先考虑计数数组，而不是哈希表。这个反射会反复用在与频率相关的题里：判断字符串字母是否互异、找数组中出现次数最多的元素、统计投票结果、检查重复字母等，底层都在做同一件事——用数组下标当数值，用数组值当频次。

一句话总结我的选择顺序：范围小且是整数，用数组；范围大、类型杂、稀疏，才考虑哈希表。做工程和刷题一样，先看约束条件再定方案，比拿到题就套数据结构要科学得多。这也是为什么我一直强调先读题目最后几行的限制条件——它经常决定了最优解的长相。

6.2 相似题型的迁移思路

LeetCode 里有不少题和 1394 共享同一套统计骨架，只是筛选项不同。举几个例子：

• 多数元素：统计频次后筛 cnt[i] > n / 2
• 第一个只出现一次的字符：统计后筛 cnt[i] == 1 并取最小下标
• 找出现奇数次的元素：统计后筛 cnt[i] % 2 == 1

它们的共同流程都是“一次统计 + 一次条件扫描”，差异只在使用哈希表还是计数数组、扫描方向、判断条件、返回什么值。这就是“模型化做题”的价值：你从一道题里抽出的是一个分析模板，而不是一段死记硬背的代码。下次遇到新题时，把模板套进去，再看看哪里需要调整，解题速度会快很多。

如果面试官想继续深挖，你可以引导出这道题的变体。比如“如果数值范围变成 10^9，计数数组开不下怎么办”，答案就切换回哈希表；“如果定义改成出现次数等于数值的两倍”，代码只需要把判断条件改成 cnt[i] == i * 2。这些临场改动都很简单，但前提是你能把基础模型讲清楚，面试官想听的往往就是这一层理解。

最后分享一个个人体会：我做这类题时，第一件事永远是看约束条件里的取值范围，而不是先读题目故事。那个数字往往比题面描述更诚实。LeetCode 1394 留给我的其实不是“用计数数组”这五个字，而是“从数据范围反推算法”这个习惯。这个习惯后来帮我解决了不少中等难度的题目，希望你也能在一次 AC 之后顺手把它带走。