LeetCode - 347. Top K Frequent Elements

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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

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.

找数组中，频率topk。

要求时间复杂度小于O(n log n)，桶排序或者堆

桶排序：

class Solution {
    public List topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length <= 0 || k <= 0)
            return new ArrayList();
        int len = nums.length;
        Map dict = new HashMap();
        for (int i=0; i) {
            if (dict.containsKey(nums[i])) {
                dict.put(nums[i], dict.get(nums[i])+1);
            } else {
                dict.put(nums[i], 1);
            }
        }
        List> bucket = new ArrayList<>(len);
        for (int i=0; i) {
            bucket.add(new ArrayList());
        }
        int max = 0;
        for (Map.Entry entry: dict.entrySet()) {
            int num = entry.getKey();
            int cnt = entry.getValue();
            if (cnt > max)
                max = cnt;
            bucket.get(cnt-1).add(num);
        }
        List ret = new ArrayList();
        for (int i=max-1; i>=0; i--) {
            List temp = bucket.get(i);
            for (int j=0; j) {
                ret.add(temp.get(j));
                if (ret.size() == k)
                    return ret;
            }
        }
        return ret;
    }
}