Skip to content

Latest commit

 

History

History
34 lines (31 loc) · 1.31 KB

347.前K个高频元素.md

File metadata and controls

34 lines (31 loc) · 1.31 KB

方法一:小顶堆排序

首先对数字出现的次数进行统计,然后建立一个小顶堆,之所以是小顶堆是因为堆顶是出现Top K次元素中出现次数最小的数字,我们插入元素的时候需要判断当前数字出现次数是否大于堆顶元素的次数,如果是的话那么应该进行替换。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int[] res = new int[k];
        int idx = 0;
        PriorityQueue<int[]> queue = new PriorityQueue(k, new Comparator<int[]>() {
            public int compare(int[] num1, int[] num2) {
                return num1[1] - num2[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.add(new int[]{entry.getKey(), entry.getValue()});
            } else if (entry.getValue() > queue.peek()[1]) {
                queue.poll();
                queue.add(new int[]{entry.getKey(), entry.getValue()});
            }
        }
        while (!queue.isEmpty()) {
            res[idx++] = queue.poll()[0];
        }
        return res;
    }
}