347. 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.

思路: 找前k个出现次数最高的元素。
用Bucket sort来做,时间复杂度O(n). 1. 先遍历一次,用hashmap建立数字-> 出现次数的map。 2. 创建bucket, 每个bucket都是一个List,把次数放入对应序号的bucket里面. 3.对bucket从后往前遍历,把适合条件的元素放入最后集合list.

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0 || k < 1) return res;
        HashMap<Integer, Integer> countDict = new HashMap<>();
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int num: nums) {
            if (!countDict.containsKey(num)) {
                countDict.put(num, 0);
            }
            int cnt = countDict.get(num);
            countDict.put(num, cnt+1);
        }
        // create frequency list
       for (int key: countDict.keySet()) {
           int frequency = countDict.get(key);
           if (bucket[frequency] == null) {
               bucket[frequency] = new ArrayList<>();
           } 
           bucket[frequency].add(key);
       }

        // add top k values to list
        for (int i = bucket.length - 1; i >= 0 && res.size() < k; i--) {
            if (bucket[i] != null) {
                res.addAll(bucket[i]);
            }
        }
        return res;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s