LeetCode.347.Top K Frequent Elements 前K个高频元素

题目描述

347 Top K Frequent Elements
https://leetcode-cn.com/problems/top-k-frequent-elements/

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

---

相似题目

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.378.Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素

LeetCode.347.Top K Frequent Elements 前K个高频元素
LeetCode.剑指offer.040.数组中最小的k个数
LeetCode.023.Merge k Sorted Lists 合并K个排序链表

---

解题过程

先用 map 统计数组中各个元素的出现次数
然后建立一个长度为K的最小堆，堆中存储 Pair(出现次数, 元素值) 并指定使用 Pair.getkey 比较
用map的前K个元素初始化，然后从第K+1个元素开始，如果大于堆顶，则删除堆顶并插入元素；如果小于堆顶，则继续读入下一个，这样最后最小堆里剩的就是频率前k大的数.

时间复杂度 O(Nlogk) ，空间复杂度 O(N)

import java.util.Comparator;
import javafx.util.Pair;

private static class SolutionV2020 {
    public List<Integer> topKFrequent(int[] nums, int k) {
        if (null == nums || 0 == nums.length) {
            return null;
        }
        // 统计数组中各个元素的出现次数  数值 -> 次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        // 最小堆，Pair<出现次数, 数值>
        // PriorityQueue<Pair<Integer, Integer>> priorityQueue = new PriorityQueue<>(k, (p1, p2) -> p1.getKey() - p2.getKey());
        PriorityQueue<Pair<Integer, Integer>> priorityQueue = new PriorityQueue<>(k, Comparator.comparingInt(Pair::getKey));
        map.forEach((key, value) -> {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(new Pair(value, key));
            } else if (value > priorityQueue.peek().getKey()) {
                priorityQueue.poll();
                priorityQueue.offer(new Pair(value, key));
            }
        });
        return priorityQueue.stream().map(Pair::getValue).collect(Collectors.toList());
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_347_TopKFrequentElements.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_347_TopKFrequentElements.java

---