LeetCode 题解工作台
找出数组中的幸运数
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。 给你一个整数数组 arr ，请你从中找出并返回一个幸运数。 如果数组中存在多个幸运数，只需返回 最大 的那个。 如果数组中不含幸运数，则返回 -1 。 示例 1： 输入： arr = [2,2,3,4] 输出： …
3
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用哈希表或数组 统计 中每个数字出现的次数，然后遍历 ，找到满足 $\textit{cnt}[x] = x$ 的最大的 即可。如果没有这样的 ，则返回 。 时间复杂度 ，空间复杂度 。其中 为 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
给你一个整数数组 arr，请你从中找出并返回一个幸运数。
- 如果数组中存在多个幸运数，只需返回 最大 的那个。
- 如果数组中不含幸运数，则返回 -1 。
示例 1：
输入：arr = [2,2,3,4] 输出：2 解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。
示例 2：
输入：arr = [1,2,2,3,3,3] 输出：3 解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。
示例 3：
输入：arr = [2,2,2,3,3] 输出：-1 解释：数组中不存在幸运数。
示例 4：
输入：arr = [5] 输出：-1
示例 5：
输入：arr = [7,7,7,7,7,7,7] 输出：7
提示：
1 <= arr.length <= 5001 <= arr[i] <= 500
解题思路
方法一：计数
我们可以用哈希表或数组 统计 中每个数字出现的次数，然后遍历 ，找到满足 的最大的 即可。如果没有这样的 ，则返回 。
时间复杂度 ，空间复杂度 。其中 为 的长度。
class Solution:
def findLucky(self, arr: List[int]) -> int:
cnt = Counter(arr)
return max((x for x, v in cnt.items() if x == v), default=-1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) to count frequencies plus O(n) to scan entries, yielding O(n) overall. Space complexity is O(n) for the hash table storing counts of integers up to the array length. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you count the frequency of each integer efficiently?
- question_mark
Have you considered returning the largest lucky integer instead of the first match?
- question_mark
Are you handling arrays where no lucky integer exists correctly?
常见陷阱
外企场景- error
Assuming the first matching integer is the largest without scanning all counts.
- error
Forgetting to check multiple integers when several satisfy the lucky condition.
- error
Not handling arrays with no lucky integers, returning an incorrect default.
进阶变体
外企场景- arrow_right_alt
Find all lucky integers instead of only the largest.
- arrow_right_alt
Determine lucky integers under constraints with very large arrays.
- arrow_right_alt
Modify the problem to find the smallest lucky integer rather than the largest.