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

示例 1:

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

示例 2:

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

提示：

1 <= nums.length <= 105 k的取值范围是[1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前k个高频元素的集合是唯一的

进阶：所设计算法的时间复杂度 必须 优于，其中是数组大小。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/g5c51o 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

使用HashMap先统计数字出现的次数。然后考虑使用大顶堆来统计前频繁出现的数字。

class Solution {

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(16);;
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
            new Comparator<int[]> () {
                @Override
                public int compare(int[] o1, int[] o2) {
                    // Java默认构造小顶堆 我们需要的是大顶堆 所以是o2-o1
                    return o2[1] - o1[1];
                }
            }
        );
        Set<Integer> keys = map.keySet();
        keys.forEach(
            key -> {
                int[] kv = new int[2];
                kv[0] = key; kv[1] = map.get(key);
                pq.add(kv);
            }
        );
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

这里使用的是优先级队列的包含比较器Comparator的构造函数。Comparable接口与Comparator接口的区别在于，Comparable主要用于实现同类之间的相互比较，而Comparator则通常用于容器中的元素进行比较。若此处优先级队列的泛型参数类实现了Comparable接口，那么构造函数中可以不用传入比较器Comparator。但我们此处存放的是一个int型的数组，所以需要实现一个Comparator接口的匿名实现类传入，以实现两个元素之间的比较。

复杂度

  • 时间复杂度：主要来自于数组扫描，和建堆的过程，应当是。
  • 空间复杂度：使用了Map和堆，复杂度是。