Java 查找整数数组中的幸运数 - 算法解析与代码实现

在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为‘幸运数’。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。 如果数组中存在多个幸运数，只需返回最大的那个。 如果数组中不含幸运数，则返回 -1 。

Java 内容： 首先，我们需要统计每个数出现的频次，可以使用哈希表来实现。然后遍历哈希表，找到频次和数值大小相等的数，并记录最大的幸运数。最后返回最大的幸运数。

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        int maxLuckyNum = -1;
        for (int num : freqMap.keySet()) {
            if (freqMap.get(num) == num && num > maxLuckyNum) {
                maxLuckyNum = num;
            }
        }
        
        return maxLuckyNum;
    }
}

时间复杂度分析： 遍历数组并统计频次的时间复杂度为 O(n)，遍历哈希表找到最大的幸运数的时间复杂度为 O(m)，其中 m 为哈希表的大小。因此，总的时间复杂度为 O(n + m)。