LeetCode 347. Top K Frequent Elements

原题链接在这里：https://leetcode.com/problems/top-k-frequent-elements/

题目：

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

题解：

先计算出element 和对应的frequency.

然后使用bucket sort. 把element按照出现频率放在bucket中.

因为一共只有n 个元素, 那么最大的频率只能是n. n = nums.length. 所以bucket的大小是n+1, 才能对应最大频率.

然后从bucket后扫到前，因为后面的elements 频率高. 加到res中直到res的size到达k.

Note: bucket的生成等号右边是ArrayList[] 而不能是ArrayList<Integer>[], 因为complier 不能判准加进ArrayList中的type, 只有run time才能知道. 所以这里complier不允许确定type.

Time Complexity: O(n), n = nums.length.

Space: O(n).

AC Java:

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums == null || nums.length == 0){
            return res;
        }
        
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for(int num : nums){
            hm.put(num, hm.getOrDefault(num, 0)+1);
        }
        
        ArrayList [] buckets= new ArrayList[nums.length+1];
        for(Map.Entry<Integer, Integer> entry : hm.entrySet()){
            int freq = entry.getValue();
            if(buckets[freq] == null){
                buckets[freq] = new ArrayList<Integer>();
            }
            buckets[freq].add(entry.getKey());
        }
        
        for(int i = buckets.length-1; i>=0 && res.size()<k; i--){
            if(buckets[i] != null){
                res.addAll(buckets[i]);
            }
        }
        
        return res;
    }
}

类似Sort Characters By Frequency, Top K Frequent Words, K Closest Points to Origin.