尧图网站建设 
LeetCode 1394 寻找数组中的幸运整数暴力、排序、哈希、负标记与位运算五种解法全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕经典频次计数问题寻找数组中的幸运整数Find Lucky Integer in an Array系统讲解五条由浅入深的解题路径暴力双循环、排序扫描、哈希表计数、原地负标记与位运算压缩存储。全文以 articles/find-lucky-integer-in-an-array.md 为骨架并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整实现与复杂度对比帮助你在一道题内打通哈希表与原地数组标记两大高频技能。读完你不仅能独立 AC 该题还能把负标记、位压缩这类技巧迁移到其他在数组中按值定位的题目如 python/0041-first-missing-positive.py 所体现的同类思路上。一、问题定义与前置知识题目要求给定一个整数数组arr一个幸运整数被定义为该整数的数值恰好等于它在数组中出现的次数。请返回数组中最大的幸运整数如果不存在返回-1。例如arr [2, 2, 3, 4]数字2出现 2 次2 2故返回2arr [1, 2, 2, 3, 3, 3]3出现 3 次返回3arr [2, 2, 2, 3, 3]2出现 3 次、3出现 2 次均不满足值 频次返回-1。在动手前需要掌握的三个基础概念也是本题的前置知识哈希表Hash Map单趟遍历即可完成频次统计key为数字、value为出现次数是本题最优解的基石数组遍历理解如何迭代数组并持续跟踪最大值max的维护频次计数将出现次数与数值本身进行比较是判断幸运整数的唯一判据。本题是一个纯频次统计 数值比较问题五种解法本质上都在回答同一个问题如何高效得到每个数出现的次数并找到值 频次的最大值区别只在于统计方式与空间开销。二、解法一暴力枚举Brute Force核心思路最直观的做法对数组中的每一个数num再扫描一遍整个数组统计它出现了多少次记为cnt。若cnt num则该数是幸运整数不断用max维护最大的那个。由于每个数都被独立地重新统计一遍复杂度为平方级。算法步骤初始化res -1表示尚未找到幸运整数遍历数组中的每个数num再次遍历整个数组统计num出现的次数cnt若cnt num令res max(res, num)返回res。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: res -1 for num in arr: cnt 0 for a in arr: if num a: cnt 1 if cnt num: res max(res, num) return respublic class Solution { public int findLucky(int[] arr) { int res -1; for (int num : arr) { int cnt 0; for (int a : arr) { if (num a) { cnt; } } if (cnt num) { res Math.max(res, num); } } return res; } }class Solution { public: int findLucky(vectorint arr) { int res -1; for (int num : arr) { int cnt 0; for (int a : arr) { if (num a) { cnt; } } if (cnt num) { res max(res, num); } } return res; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { let res -1; for (let num of arr) { let cnt 0; for (let a of arr) { if (num a) { cnt; } } if (cnt num) { res Math.max(res, num); } } return res; } }public class Solution { public int FindLucky(int[] arr) { int res -1; foreach (int num in arr) { int cnt 0; foreach (int a in arr) { if (num a) { cnt; } } if (cnt num) { res Math.Max(res, num); } } return res; } }func findLucky(arr []int) int { res : -1 for _, num : range arr { cnt : 0 for _, a : range arr { if num a { cnt } } if cnt num { if num res { res num } } } return res }class Solution { fun findLucky(arr: IntArray): Int { var res -1 for (num in arr) { var cnt 0 for (a in arr) { if (num a) { cnt } } if (cnt num) { res maxOf(res, num) } } return res } }class Solution { func findLucky(_ arr: [Int]) - Int { var res -1 for num in arr { var cnt 0 for a in arr { if num a { cnt 1 } } if cnt num { res max(res, num) } } return res } }impl Solution { pub fn find_lucky(arr: Veci32) - i32 { let mut res -1; for num in arr { let mut cnt 0; for a in arr { if num a { cnt 1; } } if cnt num { res res.max(num); } } res } }复杂度分析时间复杂度$O(n^2)$—— 外层 $n$ 个数每个数内层再扫描 $n$ 次空间复杂度$O(1)$—— 仅使用常数个变量。三、解法二排序后扫描Sorting核心思路排序后相同的数字会聚拢在一起形成一段连续块。此时从右向左遍历每遇到一个相同数字就累加连续长度streak当遇到与前一个元素不同或到达数组开头时检查streak是否等于当前元素值。由于是从大到小扫描第一个命中的幸运整数必然就是全局最大可以立即返回。算法步骤对数组排序从右向左遍历统计连续相同元素的长度streak当当前元素与前一个元素不同或已到i 0时若arr[i] streak直接返回arr[i]它一定是最大的幸运整数否则将streak清零继续扫描若遍历结束仍无命中返回-1。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: arr.sort() streak 0 for i in range(len(arr) - 1, -1, -1): streak 1 if i 0 or (arr[i] ! arr[i - 1]): if arr[i] streak: return arr[i] streak 0 return -1public class Solution { public int findLucky(int[] arr) { Arrays.sort(arr); int streak 0; for (int i arr.length - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } }class Solution { public: int findLucky(vectorint arr) { sort(arr.begin(), arr.end()); int streak 0; for (int i arr.size() - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { arr.sort((a, b) a - b); let streak 0; for (let i arr.length - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } }public class Solution { public int FindLucky(int[] arr) { Array.Sort(arr); int streak 0; for (int i arr.Length - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } }func findLucky(arr []int) int { sort.Ints(arr) streak : 0 for i : len(arr) - 1; i 0; i-- { streak if i 0 || arr[i] ! arr[i-1] { if arr[i] streak { return arr[i] } streak 0 } } return -1 }class Solution { fun findLucky(arr: IntArray): Int { arr.sort() var streak 0 for (i in arr.size - 1 downTo 0) { streak if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i] } streak 0 } } return -1 } }class Solution { func findLucky(_ arr: [Int]) - Int { let arr arr.sorted() var streak 0 for i in stride(from: arr.count - 1, through: 0, by: -1) { streak 1 if i 0 || arr[i] ! arr[i - 1] { if arr[i] streak { return arr[i] } streak 0 } } return -1 } }impl Solution { pub fn find_lucky(mut arr: Veci32) - i32 { arr.sort(); let mut streak 0; for i in (0..arr.len()).rev() { streak 1; if i 0 || arr[i] ! arr[i - 1] { if arr[i] streak { return arr[i]; } streak 0; } } -1 } }注意 JavaScript 的sort()默认按字典序排序必须显式传入比较函数(a, b) a - b才能得到正确的数值升序否则[10, 2]会被排成[10, 2]而非[2, 10]导致结果错误。复杂度分析时间复杂度$O(n \log n)$—— 主要开销在排序空间复杂度$O(1)$ 或 $O(n)$—— 取决于所用排序算法如原地快排为 $O(1)$ 或 $O(\log n)$ 栈空间归并排序则为 $O(n)$。四、解法三哈希表统计频次Hash Map核心思路暴力法低效的根源在于每个数都被重复统计。用哈希表可以在一趟遍历内完成全部频次统计以数字为键、出现次数为值。随后只需遍历哈希表的每个键值对找出键 值的最大键即可。这是空间换时间的经典体现。算法步骤一趟遍历构建频次表countcount[num]表示num出现的次数初始化res -1遍历频次表中的每一对(num, freq)若num freq令res max(res, num)返回res。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: cnt Counter(arr) res -1 for num in cnt: if num cnt[num]: res max(num, res) return respublic class Solution { public int findLucky(int[] arr) { MapInteger, Integer count new HashMap(); for (int num : arr) { count.put(num, count.getOrDefault(num, 0) 1); } int res -1; for (int num : count.keySet()) { if (num count.get(num)) { res Math.max(res, num); } } return res; } }class Solution { public: int findLucky(vectorint arr) { unordered_mapint, int count; for (int num : arr) { count[num]; } int res -1; for (auto [num, freq] : count) { if (num freq) { res max(res, num); } } return res; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { const count new Map(); for (const num of arr) { count.set(num, (count.get(num) || 0) 1); } let res -1; for (const [num, freq] of count.entries()) { if (num freq) { res Math.max(res, num); } } return res; } }public class Solution { public int FindLucky(int[] arr) { Dictionaryint, int count new Dictionaryint, int(); foreach (int num in arr) { if (!count.ContainsKey(num)) { count[num] 0; } count[num]; } int res -1; foreach (var kvp in count) { if (kvp.Key kvp.Value) { res Math.Max(res, kvp.Key); } } return res; } }func findLucky(arr []int) int { count : make(map[int]int) for _, num : range arr { count[num] } res : -1 for num, freq : range count { if num freq { if num res { res num } } } return res }class Solution { fun findLucky(arr: IntArray): Int { val count mutableMapOfInt, Int() for (num in arr) { count[num] count.getOrDefault(num, 0) 1 } var res -1 for ((num, freq) in count) { if (num freq) { res maxOf(res, num) } } return res } }class Solution { func findLucky(_ arr: [Int]) - Int { var count [Int: Int]() for num in arr { count[num, default: 0] 1 } var res -1 for (num, freq) in count { if num freq { res max(res, num) } } return res } }impl Solution { pub fn find_lucky(arr: Veci32) - i32 { let mut count HashMap::new(); for num in arr { *count.entry(num).or_insert(0) 1; } let mut res -1; for (num, freq) in count { if num freq { res res.max(num); } } res } }复杂度分析时间复杂度$O(n)$—— 一趟构建哈希表加一趟遍历键值对空间复杂度$O(n)$—— 哈希表最多存储 $n$ 个不同数字。哈希表解法是本题时间最优 代码最直观的版本也是面试中应优先给出的方案。五、解法四原地负标记Negative Marking核心思路如果允许修改输入数组可以不借助额外空间完成频次统计。由于题设中数组元素取值在1 ~ 500之间每个数字都可以映射到下标num - 1把arr[num - 1]位置打负标记并持续减 1 来累加次数。处理结束后位置i上的值-x就表示数字i 1出现了x次。这个用下标当桶、原地打负标记的思路与仓库中 python/0041-first-missing-positive.py 的原地标记手法同源先通过取负把已见过的信息编码进原数组再在第二趟遍历中读取这些标记从而把额外空间压到 $O(1)$。算法步骤对每个位置i沿着值指向下标的链式关系累加次数取出当前数字num若num在[1, n]范围内则将arr[num - 1]减 1若原本为正则先归零再减使其变为负数来记录次数沿链前进num arr[num - 1]的原始值直到回到已处理过的位置或越界从数组末尾向前遍历对每个下标i检查-arr[i] i 1即频次等于数值返回第一个命中项否则返回-1。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: n len(arr) for i in range(n): prev, num i, arr[i] while 0 num n: nxt arr[num - 1] arr[num - 1] min(0, arr[num - 1]) - 1 if num - 1 i or num - 1 prev: break prev num - 1 num nxt for i in range(n - 1, -1, -1): if -arr[i] i 1: return i 1 return -1public class Solution { public int findLucky(int[] arr) { int n arr.length; for (int i 0; i n; i) { int prev i, num arr[i]; while (0 num num n) { int nxt arr[num - 1]; arr[num - 1] Math.min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (int i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } }class Solution { public: int findLucky(vectorint arr) { int n arr.size(); for (int i 0; i n; i) { int prev i, num arr[i]; while (0 num num n) { int nxt arr[num - 1]; arr[num - 1] min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (int i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { const n arr.length; for (let i 0; i n; i) { let prev i, num arr[i]; while (0 num num n) { let nxt arr[num - 1]; arr[num - 1] Math.min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (let i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } }public class Solution { public int FindLucky(int[] arr) { int n arr.Length; for (int i 0; i n; i) { int prev i, num arr[i]; while (0 num num n) { int nxt arr[num - 1]; arr[num - 1] Math.Min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (int i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } }func findLucky(arr []int) int { n : len(arr) for i : 0; i n; i { prev, num : i, arr[i] for num 0 num n { nxt : arr[num-1] if arr[num-1] 0 { arr[num-1] -1 } else { arr[num-1]-- } if num-1 i || num-1 prev { break } prev num - 1 num nxt } } for i : n - 1; i 0; i-- { if -arr[i] i1 { return i 1 } } return -1 }class Solution { fun findLucky(arr: IntArray): Int { val n arr.size for (i in 0 until n) { var prev i var num arr[i] while (num 0 num n) { val nxt arr[num - 1] arr[num - 1] minOf(0, arr[num - 1]) - 1 if (num - 1 i || num - 1 prev) break prev num - 1 num nxt } } for (i in n - 1 downTo 0) { if (-arr[i] i 1) return i 1 } return -1 } }class Solution { func findLucky(_ arr: [Int]) - Int { var arr arr let n arr.count for i in 0..n { var prev i var num arr[i] while num 0 num n { let nxt arr[num - 1] arr[num - 1] min(0, arr[num - 1]) - 1 if num - 1 i || num - 1 prev { break } prev num - 1 num nxt } } for i in stride(from: n - 1, through: 0, by: -1) { if -arr[i] i 1 { return i 1 } } return -1 } }impl Solution { pub fn find_lucky(mut arr: Veci32) - i32 { let n arr.len() as i32; for i in 0..arr.len() { let mut prev i as i32; let mut num arr[i]; while num 0 num n { let nxt arr[(num - 1) as usize]; arr[(num - 1) as usize] arr[(num - 1) as usize].min(0) - 1; if num - 1 i as i32 || num - 1 prev { break; } prev num - 1; num nxt; } } for i in (0..arr.len()).rev() { if -arr[i] (i as i32) 1 { return (i as i32) 1; } } -1 } }复杂度分析时间复杂度$O(n)$—— 每个位置至多被链式访问常数次整体仍是线性空间复杂度$O(1)$—— 完全原地完成无额外数据结构。需要注意的是该解法会修改传入的数组。若题目环境不允许修改输入或后续还需要使用原始数组应优先选用哈希表方案同时它依赖元素取值与数组长度兼容值域映射到下标适用范围受限于数值可映射到下标区间的题设。六、解法五位运算压缩Bit Manipulation核心思路负标记的符号位只能表达是否访问过的二元信息计数则依赖连续减一。位运算法则更进一步在一个整数内同时存储原始值与频次。由于题设数值最大不超过500小于 $2^{10} 1024$低 10 位足够存原始值于是可以把频次累加在高位每次命中数字num就在arr[num - 1]上加1 10即 1024。最终读取时右移 10 位即可取出频次低位仍是原始值两者互不干扰。算法步骤遍历数组中的每个数用位掩码(1 10) - 1取出低 10 位的原始值idx若idx在数组长度范围内则令arr[idx - 1] (1 10)把出现一次累加到高位从右向左遍历数组对每个下标i右移 10 位取出频次cnt若cnt i 1返回i 1从大到小扫描第一个命中即最大幸运整数若无命中返回-1。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: for num in arr: idx num ((1 10) - 1) if idx len(arr): arr[idx - 1] (1 10) for i in range(len(arr) - 1, -1, -1): cnt arr[i] 10 if cnt i 1: return i 1 return -1public class Solution { public int findLucky(int[] arr) { for (int num : arr) { int idx num ((1 10) - 1); if (idx arr.length) { arr[idx - 1] (1 10); } } for (int i arr.length - 1; i 0; i--) { int cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } }class Solution { public: int findLucky(vectorint arr) { for (int num : arr) { int idx num ((1 10) - 1); if (idx arr.size()) { arr[idx - 1] (1 10); } } for (int i arr.size() - 1; i 0; i--) { int cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { for (let num of arr) { const idx num ((1 10) - 1); if (idx arr.length) { arr[idx - 1] 1 10; } } for (let i arr.length - 1; i 0; i--) { const cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } }public class Solution { public int FindLucky(int[] arr) { foreach (int num in arr) { int idx num ((1 10) - 1); if (idx arr.Length) { arr[idx - 1] (1 10); } } for (int i arr.Length - 1; i 0; i--) { int cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } }func findLucky(arr []int) int { for _, num : range arr { idx : num ((1 10) - 1) if idx len(arr) { arr[idx-1] (1 10) } } for i : len(arr) - 1; i 0; i-- { cnt : arr[i] 10 if cnt i1 { return i 1 } } return -1 }class Solution { fun findLucky(arr: IntArray): Int { for (num in arr) { val idx num and ((1 shl 10) - 1) if (idx arr.size) { arr[idx - 1] (1 shl 10) } } for (i in arr.size - 1 downTo 0) { val cnt arr[i] shr 10 if (cnt i 1) return i 1 } return -1 } }class Solution { func findLucky(_ arr: [Int]) - Int { var arr arr for num in arr { let idx num ((1 10) - 1) if idx arr.count { arr[idx - 1] (1 10) } } for i in stride(from: arr.count - 1, through: 0, by: -1) { let cnt arr[i] 10 if cnt i 1 { return i 1 } } return -1 } }impl Solution { pub fn find_lucky(mut arr: Veci32) - i32 { let n arr.len(); for i in 0..n { let idx (arr[i] ((1 10) - 1)) as usize; if idx 1 idx n { arr[idx - 1] 1 10; } } for i in (0..n).rev() { let cnt arr[i] 10; if cnt (i as i32) 1 { return (i as i32) 1; } } -1 } }复杂度分析时间复杂度$O(n)$—— 一趟统计加一趟扫描空间复杂度$O(1)$—— 原地完成。适用前提与边界位运算法成立依赖两个条件缺一不可值域必须能放进低 10 位题目约束arr[i] 500 1024因此 10 位掩码足够若数值可能超过 1023需要相应扩大掩码位数或改用其他方案i32整数位宽足够当n很大时高位频次累加可能与低位原始值在 32 位内产生溢出风险需根据题目数据范围评估与负标记法一样该方法会修改输入数组把每个元素整体抬高1024的倍数同样不适合要求不得改动输入的场景。七、五种解法横向对比解法核心思想时间复杂度空间复杂度是否修改输入适用场景暴力枚举每个数重新扫描统计$O(n^2)$$O(1)$否数据量极小、仅需演示思路排序扫描排序后连续块统计$O(n \log n)$$O(1)$ / $O(n)$是原地排序面试追问、不介意排序哈希表一趟建频次表$O(n)$$O(n)$否通用首选直观且时间最优原地负标记下标当桶、负号计数$O(n)$$O(1)$是允许修改输入且追求零额外空间位运算压缩高低位分别存值与频次$O(n)$$O(1)$是值域受限、位运算爱好者/竞赛场景选型建议实际编码与面试中最推荐哈希表——思路清晰、不易出错、时间最优若面试官追问能否把空间降到 $O(1)$再依次引出排序法与两种原地标记法即可覆盖从基础到进阶的完整能力展示。八、常见陷阱Common Pitfalls陷阱一忘记处理不存在幸运整数的情况幸运整数的存在要求某数的值恰好等于其出现次数这是相当苛刻的条件。例如输入[1, 1]数字1出现 2 次1 ! 2没有任何幸运整数必须返回-1。若初始化结果时忘记设为-1或遗漏无命中时返回 -1的分支就会输出错误答案。五种解法中暴力法、哈希法用res -1兜底排序法、负标记法、位运算法则用遍历结束返回 -1兜底务必保留这一分支。陷阱二未返回最大的幸运整数数组中可能同时存在多个幸运整数例如[1, 1, 2, 2, 2]中1出现 2 次、2出现 3 次二者均不满足但若构造[2, 2, 3, 3, 3]2与3同为幸运整数题目要求返回最大的那个。如果只返回第一个找到的幸运整数就会产生错误暴力法、哈希表法必须用max(res, num)持续比较排序法、负标记法、位运算法利用从大到小扫描的次序第一个命中即可立即返回这正是它们不需要额外维护最大值的原因。九、总结寻找数组中的幸运整数是一个频次计数问题的绝佳教学样本五条解法覆盖了从 $O(n^2)$ 到 $O(n)$ 的时间演进以及从 $O(n)$ 到 $O(1)$ 的空间压缩路径串联起哈希表、排序、原地负标记、位运算四大核心技巧。阅读本文后你可以对照 articles/find-lucky-integer-in-an-array.md 中的多语言代码逐行验证也可以在本仓库按语言目录如 python/、cpp/、java/、javascript/、go/、rust/、swift/、kotlin/、csharp/查阅更多同类型题解把原地标记 值域映射的方法论迁移到其他数组处理问题上。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1394 寻找数组中的幸运整数：暴力、排序、哈希、负标记与位运算五种解法全解析
LeetCode 1394 寻找数组中的幸运整数暴力、排序、哈希、负标记与位运算五种解法全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕经典频次计数问题寻找数组中的幸运整数Find Lucky Integer in an Array系统讲解五条由浅入深的解题路径暴力双循环、排序扫描、哈希表计数、原地负标记与位运算压缩存储。全文以 articles/find-lucky-integer-in-an-array.md 为骨架并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整实现与复杂度对比帮助你在一道题内打通哈希表与原地数组标记两大高频技能。读完你不仅能独立 AC 该题还能把负标记、位压缩这类技巧迁移到其他在数组中按值定位的题目如 python/0041-first-missing-positive.py 所体现的同类思路上。一、问题定义与前置知识题目要求给定一个整数数组arr一个幸运整数被定义为该整数的数值恰好等于它在数组中出现的次数。请返回数组中最大的幸运整数如果不存在返回-1。例如arr [2, 2, 3, 4]数字2出现 2 次2 2故返回2arr [1, 2, 2, 3, 3, 3]3出现 3 次返回3arr [2, 2, 2, 3, 3]2出现 3 次、3出现 2 次均不满足值 频次返回-1。在动手前需要掌握的三个基础概念也是本题的前置知识哈希表Hash Map单趟遍历即可完成频次统计key为数字、value为出现次数是本题最优解的基石数组遍历理解如何迭代数组并持续跟踪最大值max的维护频次计数将出现次数与数值本身进行比较是判断幸运整数的唯一判据。本题是一个纯频次统计 数值比较问题五种解法本质上都在回答同一个问题如何高效得到每个数出现的次数并找到值 频次的最大值区别只在于统计方式与空间开销。二、解法一暴力枚举Brute Force核心思路最直观的做法对数组中的每一个数num再扫描一遍整个数组统计它出现了多少次记为cnt。若cnt num则该数是幸运整数不断用max维护最大的那个。由于每个数都被独立地重新统计一遍复杂度为平方级。算法步骤初始化res -1表示尚未找到幸运整数遍历数组中的每个数num再次遍历整个数组统计num出现的次数cnt若cnt num令res max(res, num)返回res。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: res -1 for num in arr: cnt 0 for a in arr: if num a: cnt 1 if cnt num: res max(res, num) return respublic class Solution { public int findLucky(int[] arr) { int res -1; for (int num : arr) { int cnt 0; for (int a : arr) { if (num a) { cnt; } } if (cnt num) { res Math.max(res, num); } } return res; } }class Solution { public: int findLucky(vectorint arr) { int res -1; for (int num : arr) { int cnt 0; for (int a : arr) { if (num a) { cnt; } } if (cnt num) { res max(res, num); } } return res; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { let res -1; for (let num of arr) { let cnt 0; for (let a of arr) { if (num a) { cnt; } } if (cnt num) { res Math.max(res, num); } } return res; } }public class Solution { public int FindLucky(int[] arr) { int res -1; foreach (int num in arr) { int cnt 0; foreach (int a in arr) { if (num a) { cnt; } } if (cnt num) { res Math.Max(res, num); } } return res; } }func findLucky(arr []int) int { res : -1 for _, num : range arr { cnt : 0 for _, a : range arr { if num a { cnt } } if cnt num { if num res { res num } } } return res }class Solution { fun findLucky(arr: IntArray): Int { var res -1 for (num in arr) { var cnt 0 for (a in arr) { if (num a) { cnt } } if (cnt num) { res maxOf(res, num) } } return res } }class Solution { func findLucky(_ arr: [Int]) - Int { var res -1 for num in arr { var cnt 0 for a in arr { if num a { cnt 1 } } if cnt num { res max(res, num) } } return res } }impl Solution { pub fn find_lucky(arr: Veci32) - i32 { let mut res -1; for num in arr { let mut cnt 0; for a in arr { if num a { cnt 1; } } if cnt num { res res.max(num); } } res } }复杂度分析时间复杂度$O(n^2)$—— 外层 $n$ 个数每个数内层再扫描 $n$ 次空间复杂度$O(1)$—— 仅使用常数个变量。三、解法二排序后扫描Sorting核心思路排序后相同的数字会聚拢在一起形成一段连续块。此时从右向左遍历每遇到一个相同数字就累加连续长度streak当遇到与前一个元素不同或到达数组开头时检查streak是否等于当前元素值。由于是从大到小扫描第一个命中的幸运整数必然就是全局最大可以立即返回。算法步骤对数组排序从右向左遍历统计连续相同元素的长度streak当当前元素与前一个元素不同或已到i 0时若arr[i] streak直接返回arr[i]它一定是最大的幸运整数否则将streak清零继续扫描若遍历结束仍无命中返回-1。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: arr.sort() streak 0 for i in range(len(arr) - 1, -1, -1): streak 1 if i 0 or (arr[i] ! arr[i - 1]): if arr[i] streak: return arr[i] streak 0 return -1public class Solution { public int findLucky(int[] arr) { Arrays.sort(arr); int streak 0; for (int i arr.length - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } }class Solution { public: int findLucky(vectorint arr) { sort(arr.begin(), arr.end()); int streak 0; for (int i arr.size() - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { arr.sort((a, b) a - b); let streak 0; for (let i arr.length - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } }public class Solution { public int FindLucky(int[] arr) { Array.Sort(arr); int streak 0; for (int i arr.Length - 1; i 0; i--) { streak; if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i]; } streak 0; } } return -1; } }func findLucky(arr []int) int { sort.Ints(arr) streak : 0 for i : len(arr) - 1; i 0; i-- { streak if i 0 || arr[i] ! arr[i-1] { if arr[i] streak { return arr[i] } streak 0 } } return -1 }class Solution { fun findLucky(arr: IntArray): Int { arr.sort() var streak 0 for (i in arr.size - 1 downTo 0) { streak if (i 0 || arr[i] ! arr[i - 1]) { if (arr[i] streak) { return arr[i] } streak 0 } } return -1 } }class Solution { func findLucky(_ arr: [Int]) - Int { let arr arr.sorted() var streak 0 for i in stride(from: arr.count - 1, through: 0, by: -1) { streak 1 if i 0 || arr[i] ! arr[i - 1] { if arr[i] streak { return arr[i] } streak 0 } } return -1 } }impl Solution { pub fn find_lucky(mut arr: Veci32) - i32 { arr.sort(); let mut streak 0; for i in (0..arr.len()).rev() { streak 1; if i 0 || arr[i] ! arr[i - 1] { if arr[i] streak { return arr[i]; } streak 0; } } -1 } }注意 JavaScript 的sort()默认按字典序排序必须显式传入比较函数(a, b) a - b才能得到正确的数值升序否则[10, 2]会被排成[10, 2]而非[2, 10]导致结果错误。复杂度分析时间复杂度$O(n \log n)$—— 主要开销在排序空间复杂度$O(1)$ 或 $O(n)$—— 取决于所用排序算法如原地快排为 $O(1)$ 或 $O(\log n)$ 栈空间归并排序则为 $O(n)$。四、解法三哈希表统计频次Hash Map核心思路暴力法低效的根源在于每个数都被重复统计。用哈希表可以在一趟遍历内完成全部频次统计以数字为键、出现次数为值。随后只需遍历哈希表的每个键值对找出键 值的最大键即可。这是空间换时间的经典体现。算法步骤一趟遍历构建频次表countcount[num]表示num出现的次数初始化res -1遍历频次表中的每一对(num, freq)若num freq令res max(res, num)返回res。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: cnt Counter(arr) res -1 for num in cnt: if num cnt[num]: res max(num, res) return respublic class Solution { public int findLucky(int[] arr) { MapInteger, Integer count new HashMap(); for (int num : arr) { count.put(num, count.getOrDefault(num, 0) 1); } int res -1; for (int num : count.keySet()) { if (num count.get(num)) { res Math.max(res, num); } } return res; } }class Solution { public: int findLucky(vectorint arr) { unordered_mapint, int count; for (int num : arr) { count[num]; } int res -1; for (auto [num, freq] : count) { if (num freq) { res max(res, num); } } return res; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { const count new Map(); for (const num of arr) { count.set(num, (count.get(num) || 0) 1); } let res -1; for (const [num, freq] of count.entries()) { if (num freq) { res Math.max(res, num); } } return res; } }public class Solution { public int FindLucky(int[] arr) { Dictionaryint, int count new Dictionaryint, int(); foreach (int num in arr) { if (!count.ContainsKey(num)) { count[num] 0; } count[num]; } int res -1; foreach (var kvp in count) { if (kvp.Key kvp.Value) { res Math.Max(res, kvp.Key); } } return res; } }func findLucky(arr []int) int { count : make(map[int]int) for _, num : range arr { count[num] } res : -1 for num, freq : range count { if num freq { if num res { res num } } } return res }class Solution { fun findLucky(arr: IntArray): Int { val count mutableMapOfInt, Int() for (num in arr) { count[num] count.getOrDefault(num, 0) 1 } var res -1 for ((num, freq) in count) { if (num freq) { res maxOf(res, num) } } return res } }class Solution { func findLucky(_ arr: [Int]) - Int { var count [Int: Int]() for num in arr { count[num, default: 0] 1 } var res -1 for (num, freq) in count { if num freq { res max(res, num) } } return res } }impl Solution { pub fn find_lucky(arr: Veci32) - i32 { let mut count HashMap::new(); for num in arr { *count.entry(num).or_insert(0) 1; } let mut res -1; for (num, freq) in count { if num freq { res res.max(num); } } res } }复杂度分析时间复杂度$O(n)$—— 一趟构建哈希表加一趟遍历键值对空间复杂度$O(n)$—— 哈希表最多存储 $n$ 个不同数字。哈希表解法是本题时间最优 代码最直观的版本也是面试中应优先给出的方案。五、解法四原地负标记Negative Marking核心思路如果允许修改输入数组可以不借助额外空间完成频次统计。由于题设中数组元素取值在1 ~ 500之间每个数字都可以映射到下标num - 1把arr[num - 1]位置打负标记并持续减 1 来累加次数。处理结束后位置i上的值-x就表示数字i 1出现了x次。这个用下标当桶、原地打负标记的思路与仓库中 python/0041-first-missing-positive.py 的原地标记手法同源先通过取负把已见过的信息编码进原数组再在第二趟遍历中读取这些标记从而把额外空间压到 $O(1)$。算法步骤对每个位置i沿着值指向下标的链式关系累加次数取出当前数字num若num在[1, n]范围内则将arr[num - 1]减 1若原本为正则先归零再减使其变为负数来记录次数沿链前进num arr[num - 1]的原始值直到回到已处理过的位置或越界从数组末尾向前遍历对每个下标i检查-arr[i] i 1即频次等于数值返回第一个命中项否则返回-1。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: n len(arr) for i in range(n): prev, num i, arr[i] while 0 num n: nxt arr[num - 1] arr[num - 1] min(0, arr[num - 1]) - 1 if num - 1 i or num - 1 prev: break prev num - 1 num nxt for i in range(n - 1, -1, -1): if -arr[i] i 1: return i 1 return -1public class Solution { public int findLucky(int[] arr) { int n arr.length; for (int i 0; i n; i) { int prev i, num arr[i]; while (0 num num n) { int nxt arr[num - 1]; arr[num - 1] Math.min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (int i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } }class Solution { public: int findLucky(vectorint arr) { int n arr.size(); for (int i 0; i n; i) { int prev i, num arr[i]; while (0 num num n) { int nxt arr[num - 1]; arr[num - 1] min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (int i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { const n arr.length; for (let i 0; i n; i) { let prev i, num arr[i]; while (0 num num n) { let nxt arr[num - 1]; arr[num - 1] Math.min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (let i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } }public class Solution { public int FindLucky(int[] arr) { int n arr.Length; for (int i 0; i n; i) { int prev i, num arr[i]; while (0 num num n) { int nxt arr[num - 1]; arr[num - 1] Math.Min(0, arr[num - 1]) - 1; if (num - 1 i || num - 1 prev) break; prev num - 1; num nxt; } } for (int i n - 1; i 0; i--) { if (-arr[i] i 1) return i 1; } return -1; } }func findLucky(arr []int) int { n : len(arr) for i : 0; i n; i { prev, num : i, arr[i] for num 0 num n { nxt : arr[num-1] if arr[num-1] 0 { arr[num-1] -1 } else { arr[num-1]-- } if num-1 i || num-1 prev { break } prev num - 1 num nxt } } for i : n - 1; i 0; i-- { if -arr[i] i1 { return i 1 } } return -1 }class Solution { fun findLucky(arr: IntArray): Int { val n arr.size for (i in 0 until n) { var prev i var num arr[i] while (num 0 num n) { val nxt arr[num - 1] arr[num - 1] minOf(0, arr[num - 1]) - 1 if (num - 1 i || num - 1 prev) break prev num - 1 num nxt } } for (i in n - 1 downTo 0) { if (-arr[i] i 1) return i 1 } return -1 } }class Solution { func findLucky(_ arr: [Int]) - Int { var arr arr let n arr.count for i in 0..n { var prev i var num arr[i] while num 0 num n { let nxt arr[num - 1] arr[num - 1] min(0, arr[num - 1]) - 1 if num - 1 i || num - 1 prev { break } prev num - 1 num nxt } } for i in stride(from: n - 1, through: 0, by: -1) { if -arr[i] i 1 { return i 1 } } return -1 } }impl Solution { pub fn find_lucky(mut arr: Veci32) - i32 { let n arr.len() as i32; for i in 0..arr.len() { let mut prev i as i32; let mut num arr[i]; while num 0 num n { let nxt arr[(num - 1) as usize]; arr[(num - 1) as usize] arr[(num - 1) as usize].min(0) - 1; if num - 1 i as i32 || num - 1 prev { break; } prev num - 1; num nxt; } } for i in (0..arr.len()).rev() { if -arr[i] (i as i32) 1 { return (i as i32) 1; } } -1 } }复杂度分析时间复杂度$O(n)$—— 每个位置至多被链式访问常数次整体仍是线性空间复杂度$O(1)$—— 完全原地完成无额外数据结构。需要注意的是该解法会修改传入的数组。若题目环境不允许修改输入或后续还需要使用原始数组应优先选用哈希表方案同时它依赖元素取值与数组长度兼容值域映射到下标适用范围受限于数值可映射到下标区间的题设。六、解法五位运算压缩Bit Manipulation核心思路负标记的符号位只能表达是否访问过的二元信息计数则依赖连续减一。位运算法则更进一步在一个整数内同时存储原始值与频次。由于题设数值最大不超过500小于 $2^{10} 1024$低 10 位足够存原始值于是可以把频次累加在高位每次命中数字num就在arr[num - 1]上加1 10即 1024。最终读取时右移 10 位即可取出频次低位仍是原始值两者互不干扰。算法步骤遍历数组中的每个数用位掩码(1 10) - 1取出低 10 位的原始值idx若idx在数组长度范围内则令arr[idx - 1] (1 10)把出现一次累加到高位从右向左遍历数组对每个下标i右移 10 位取出频次cnt若cnt i 1返回i 1从大到小扫描第一个命中即最大幸运整数若无命中返回-1。多语言实现class Solution: def findLucky(self, arr: List[int]) - int: for num in arr: idx num ((1 10) - 1) if idx len(arr): arr[idx - 1] (1 10) for i in range(len(arr) - 1, -1, -1): cnt arr[i] 10 if cnt i 1: return i 1 return -1public class Solution { public int findLucky(int[] arr) { for (int num : arr) { int idx num ((1 10) - 1); if (idx arr.length) { arr[idx - 1] (1 10); } } for (int i arr.length - 1; i 0; i--) { int cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } }class Solution { public: int findLucky(vectorint arr) { for (int num : arr) { int idx num ((1 10) - 1); if (idx arr.size()) { arr[idx - 1] (1 10); } } for (int i arr.size() - 1; i 0; i--) { int cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } };class Solution { /** * param {number[]} arr * return {number} */ findLucky(arr) { for (let num of arr) { const idx num ((1 10) - 1); if (idx arr.length) { arr[idx - 1] 1 10; } } for (let i arr.length - 1; i 0; i--) { const cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } }public class Solution { public int FindLucky(int[] arr) { foreach (int num in arr) { int idx num ((1 10) - 1); if (idx arr.Length) { arr[idx - 1] (1 10); } } for (int i arr.Length - 1; i 0; i--) { int cnt arr[i] 10; if (cnt i 1) return i 1; } return -1; } }func findLucky(arr []int) int { for _, num : range arr { idx : num ((1 10) - 1) if idx len(arr) { arr[idx-1] (1 10) } } for i : len(arr) - 1; i 0; i-- { cnt : arr[i] 10 if cnt i1 { return i 1 } } return -1 }class Solution { fun findLucky(arr: IntArray): Int { for (num in arr) { val idx num and ((1 shl 10) - 1) if (idx arr.size) { arr[idx - 1] (1 shl 10) } } for (i in arr.size - 1 downTo 0) { val cnt arr[i] shr 10 if (cnt i 1) return i 1 } return -1 } }class Solution { func findLucky(_ arr: [Int]) - Int { var arr arr for num in arr { let idx num ((1 10) - 1) if idx arr.count { arr[idx - 1] (1 10) } } for i in stride(from: arr.count - 1, through: 0, by: -1) { let cnt arr[i] 10 if cnt i 1 { return i 1 } } return -1 } }impl Solution { pub fn find_lucky(mut arr: Veci32) - i32 { let n arr.len(); for i in 0..n { let idx (arr[i] ((1 10) - 1)) as usize; if idx 1 idx n { arr[idx - 1] 1 10; } } for i in (0..n).rev() { let cnt arr[i] 10; if cnt (i as i32) 1 { return (i as i32) 1; } } -1 } }复杂度分析时间复杂度$O(n)$—— 一趟统计加一趟扫描空间复杂度$O(1)$—— 原地完成。适用前提与边界位运算法成立依赖两个条件缺一不可值域必须能放进低 10 位题目约束arr[i] 500 1024因此 10 位掩码足够若数值可能超过 1023需要相应扩大掩码位数或改用其他方案i32整数位宽足够当n很大时高位频次累加可能与低位原始值在 32 位内产生溢出风险需根据题目数据范围评估与负标记法一样该方法会修改输入数组把每个元素整体抬高1024的倍数同样不适合要求不得改动输入的场景。七、五种解法横向对比解法核心思想时间复杂度空间复杂度是否修改输入适用场景暴力枚举每个数重新扫描统计$O(n^2)$$O(1)$否数据量极小、仅需演示思路排序扫描排序后连续块统计$O(n \log n)$$O(1)$ / $O(n)$是原地排序面试追问、不介意排序哈希表一趟建频次表$O(n)$$O(n)$否通用首选直观且时间最优原地负标记下标当桶、负号计数$O(n)$$O(1)$是允许修改输入且追求零额外空间位运算压缩高低位分别存值与频次$O(n)$$O(1)$是值域受限、位运算爱好者/竞赛场景选型建议实际编码与面试中最推荐哈希表——思路清晰、不易出错、时间最优若面试官追问能否把空间降到 $O(1)$再依次引出排序法与两种原地标记法即可覆盖从基础到进阶的完整能力展示。八、常见陷阱Common Pitfalls陷阱一忘记处理不存在幸运整数的情况幸运整数的存在要求某数的值恰好等于其出现次数这是相当苛刻的条件。例如输入[1, 1]数字1出现 2 次1 ! 2没有任何幸运整数必须返回-1。若初始化结果时忘记设为-1或遗漏无命中时返回 -1的分支就会输出错误答案。五种解法中暴力法、哈希法用res -1兜底排序法、负标记法、位运算法则用遍历结束返回 -1兜底务必保留这一分支。陷阱二未返回最大的幸运整数数组中可能同时存在多个幸运整数例如[1, 1, 2, 2, 2]中1出现 2 次、2出现 3 次二者均不满足但若构造[2, 2, 3, 3, 3]2与3同为幸运整数题目要求返回最大的那个。如果只返回第一个找到的幸运整数就会产生错误暴力法、哈希表法必须用max(res, num)持续比较排序法、负标记法、位运算法利用从大到小扫描的次序第一个命中即可立即返回这正是它们不需要额外维护最大值的原因。九、总结寻找数组中的幸运整数是一个频次计数问题的绝佳教学样本五条解法覆盖了从 $O(n^2)$ 到 $O(n)$ 的时间演进以及从 $O(n)$ 到 $O(1)$ 的空间压缩路径串联起哈希表、排序、原地负标记、位运算四大核心技巧。阅读本文后你可以对照 articles/find-lucky-integer-in-an-array.md 中的多语言代码逐行验证也可以在本仓库按语言目录如 python/、cpp/、java/、javascript/、go/、rust/、swift/、kotlin/、csharp/查阅更多同类型题解把原地标记 值域映射的方法论迁移到其他数组处理问题上。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考