每日力扣——滑动窗口与前 K 个高频元素-最大值

问题分析

我们首先分析了问题的输入、输出和约束条件：

• 输入：给定一个非空的整数数组 nums 和一个正整数 k。
• 输出：返回出现频率前 k 高的元素的集合。
• 约束条件：给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

算法思路

解决出现频率前 k 高的元素问题的一般思路如下：

• 首先，我们可以使用哈希表统计数组中每个元素的频率。
• 然后，我们可以使用最小堆（优先队列）来找到频率前 k 高的元素。

public class TopKFrequentElements {

    public static int[] topKFrequent(int[] nums, int k) {
        // 使用哈希表统计每个元素的频率
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 使用最小堆找到频率前 k 高的元素
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
                new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 构建结果数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = Objects.requireNonNull(minHeap.poll()).getKey();
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        int k1 = 2;
        System.out.println(Arrays.toString(topKFrequent(nums1, k1))); // Output: [1, 2]

        int[] nums2 = {1};
        int k2 = 1;
        System.out.println(Arrays.toString(topKFrequent(nums2, k2))); // Output: [1]
    }
}