Leetcode:347. 前 K 个高频元素

题目描述

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

示例 1:

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

示例 2:

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

说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小

思路

思路1

维护一个大小为K的最小堆，根据数字出现次数排序

思路2

使用桶排序，维护一个出现次数的二维数组

代码

代码1

class Solution {
    public List topKFrequent(int[] nums, int k) {
        Map map = new HashMap();
        for(int num: nums){
            if (!map.containsKey(num)){
                map.put(num, 1);
            } else{
                map.put(num, map.get(num) + 1);
            }
        }

        PriorityQueue pq =
                new PriorityQueue((n1, n2) -> map.get(n1) - map.get(n2));
        for(int num: map.keySet()){
            pq.add(num);
            if (pq.size() > k){
                pq.poll();
            }
        }

        List maxQueue = new ArrayList<>();
        while (pq.size() != 0){
            maxQueue.add(pq.poll());
        }
        Collections.reverse(maxQueue);
        return maxQueue;
    }
}

代码2

class Solution {
    public List topKFrequent(int[] nums, int k) {
        Map map = new HashMap();
        for(int num: nums){
            if (!map.containsKey(num)){
                map.put(num, 1);
            } else{
                map.put(num, map.get(num) + 1);
            }
        }
        
        List[] sizeCount = new List[nums.length];
        
        for(int num: map.keySet()){
            int getCount = map.get(num) - 1;
            if (sizeCount[getCount] == null){
                sizeCount[getCount] = new ArrayList();
            }
            sizeCount[getCount].add(num);
        }
        
        List maxQueue = new ArrayList<>();
        for(int i = nums.length - 1; i >= 0 && maxQueue.size() < k; i--){
            if (sizeCount[i] == null){
                continue;
            }else {
                maxQueue.addAll(sizeCount[i]);
            }
        }
        return maxQueue;
    }
}