Easy

题目描述

给你一个整数数组 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
解释：数组中不存在幸运数。

提示：

  • 1 <= arr.length <= 500
  • 1 <= arr[i] <= 500

提示：

  • 统计数组中每个整数的出现次数
  • 获取所有幸运数并返回其中最大的

解题思路

这道题的核心思路是统计频次并寻找满足条件的数值。

解题思路：

  1. 频次统计：遍历数组，统计每个数字的出现次数。可以使用哈希表来实现这一步。

  2. 查找幸运数：遍历频次统计的结果，找出所有满足"数值等于出现次数"的数字，这些就是幸运数。

  3. 返回最大值：在所有幸运数中返回最大的一个。如果没有幸运数，返回-1。

算法实现细节：

  • 使用哈希表记录每个数字的频次
  • 遍历哈希表，检查每个键值对是否满足 key == value 的条件
  • 维护一个最大幸运数变量，初始化为-1
  • 当找到幸运数时，更新最大值

时间复杂度优化： 由于题目限制了数值范围在1-500之间，也可以使用数组代替哈希表进行频次统计，但哈希表的写法更通用。

这个解法简洁高效，一次遍历统计频次，一次遍历查找结果，总体时间复杂度为O(n)。

代码实现

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> freq;
        
        // 统计每个数字的频次
        for (int num : arr) {
            freq[num]++;
        }
        
        int lucky = -1;
        // 找到最大的幸运数
        for (auto& [num, count] : freq) {
            if (num == count) {
                lucky = max(lucky, num);
            }
        }
        
        return lucky;
    }
};

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        from collections import Counter
        
        # 统计每个数字的频次
        freq = Counter(arr)
        
        lucky = -1
        # 找到最大的幸运数
        for num, count in freq.items():
            if num == count:
                lucky = max(lucky, num)
        
        return lucky

public class Solution {
    public int FindLucky(int[] arr) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        // 统计每个数字的频次
        foreach (int num in arr) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
        }
        
        int lucky = -1;
        // 找到最大的幸运数
        foreach (var pair in freq) {
            if (pair.Key == pair.Value) {
                lucky = Math.Max(lucky, pair.Key);
            }
        }
        
        return lucky;
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var findLucky = function(arr) {
    const freq = {};
    for (let num of arr) {
        freq[num] = (freq[num] || 0) + 1;
    }
    
    let lucky = -1;
    for (let num in freq) {
        if (parseInt(num) === freq[num]) {
            lucky = Math.max(lucky, parseInt(num));
        }
    }
    
    return lucky;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次统计频次，再遍历哈希表一次查找幸运数，其中n是数组长度
空间复杂度O(k)哈希表存储不同数字的频次，k为数组中不同数字的个数，最坏情况下k=n