题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

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

题目分析

先统计出每个元素出现的次数，再使用优先队列维护 k 个最大次数的元素。
时间复杂度 O(n * log k)

Java

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(map.getOrDefault(o1, 0), map.getOrDefault(o2, 0)));
    for (int n : nums) {
        map.put(n, map.getOrDefault(n, 0) + 1);
    }
    for (int n : map.keySet()) {
        queue.offer(n);
        if (queue.size() > k) {
            queue.poll();
        }
    }
    int size = queue.size();
    int[] ans = new int[size];
    for (int i = 0; i < size; i++) {
        ans[i] = queue.poll();
    }
    return ans;
}

Kotlin

fun topKFrequent(nums: IntArray, k: Int): IntArray {
    val map = HashMap<Int, Int>()
    val queue = PriorityQueue<Int> { o1, o2 -> Integer.compare(map.getOrDefault(o1, 0), map.getOrDefault(o2, 0)) }
    for (n in nums) {
        map[n] = (map[n] ?: 0) + 1
    }
    for (n in map.keys) {
        queue.offer(n)
        if (queue.size > k) {
            queue.poll()
        }
    }

    return queue.toIntArray()
}