TechNomads

题目

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

解法

利用hash表记录每个元素出现的次数，维护一个k大的优先队列， 优先队列中维护每个元素及出现次数，根据出现次数排序，取前K个即可。

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for(int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<int []> queue = new PriorityQueue<>(new Comparator<int []>() {
            public int compare(int m[], int n[]) {
                return m[1] - n[1];
            }
        });

        countMap.forEach((num, count) -> {
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int [] {num, count});
                }
            } else {
                queue.offer(new int [] {num, count});
            }
        });

        int [] res = new int [k];
        for(int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }

运行结果：