Top K Frequent Elements

目的是练习如何写priority queue 和 treemap

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.

Three Ways

Priority Queue time: O(nlogk) space O(n)

TreeMap : time: O(klogn) space O(n)

Bucket Sort : time O(n) space O(n)

• [x] time O(nlogk) why? beacause you insert n elements and every time the insert takes logk time

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer>[] bucket = new List[nums.length + 1];
        List<Integer> ans = new ArrayList<>();
        if (nums == null|| nums.length ==0) {
            return ans;
        }
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (freqMap.containsKey(nums[i])) {
                freqMap.put(nums[i], freqMap.get(nums[i]) + 1);
            }else{
                freqMap.put(nums[i], 1);
            }
        }
        for (int key : freqMap.keySet()) {
            int freq = freqMap.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<Integer>();
            }
            bucket[freq].add(key);
        }
        for(int i = bucket.length - 1; i >= 0 && ans.size() < k; i--) {
            if (bucket[i] != null) {
                ans.addAll(bucket[i]);
            }
        }
        return ans;
    } 
}

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        // count the frequent of each number 
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            }else {
                map.put(nums[i], 1);
            }
        } 
        //use priorityqueue to sort the freq
        //time O(nlogk) why? beacause you insert n elements and every time the insert takes logk time 
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        //pop up k answers
        while (!minHeap.isEmpty()) {
            Map.Entry<Integer, Integer> list = minHeap.poll();
            ans.add(list.getKey());
        }
        return ans;
    }
}

solution 3 : treemap

one para:

while (ans.size() < k) {
   Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
   ans.addAll(entry.getValue());
}

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        // count the frequent of each number 
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            }else {
                map.put(nums[i], 1);
            }
        } 
        TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
        for (int key : map.keySet()) {
            int freq = map.get(key);
            if (freqMap.containsKey(freq)) {
                freqMap.get(freq).add(key);
            }else{
                freqMap.put(freq, new ArrayList<Integer>());
                freqMap.get(freq).add(key);
            }
        }
        while (ans.size() < k) {
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            ans.addAll(entry.getValue());
        }
        return ans;
    }
}