347. Top K Frequent Elements

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.

My Solutions:

Time < O(nlgn) 必然是 O(n)。必然用吊桶，不需要priority queue排序

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i : nums) {
            hash.put(i, hash.getOrDefault(i, 0) + 1);
        }
        
        //use bucket to store numbers by frequency
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
        for (int i : hash.keySet()) {
            int count = hash.get(i);
            if (bucket[count] == null) bucket[count] = new ArrayList<>();
            bucket[count].add(i);
        }
        
        List<Integer> res = new ArrayList<>();
        for (int i = bucket.length - 1; i > 0 & k > 0; i--) {
            List<Integer> list = bucket[i];
            int j = 0;
            while (list != null && j < list.size() && k > 0){
                res.add(list.get(j++));
                k--;
            }
        }
        return res;
    }
}

用priority queue的方法如下：

    public int[] topKFrequent(int[] nums, int k) {
    
        // build a hashp map of number and it's frequency
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        
        // init a heap: the less frequent first
        // The comparator, count.get(n1) - count.get(n2), evaluates to -1, 0, or 1depending on which number is bigger. If the result is -1 then n1 must be "smaller" and thus gets placed closer to the head of the queue than n2.
        Queue<Integer> heap = new PriorityQueue<>(
        (n1, n2) -> map.get(n1) - map.get(n2));
        
        // keep the k top frequent elements in the heap
        for (int n : map.keySet()) {
            heap.add(n);
            if (heap.size() > k) heap.poll();
        }
        
        // build an output
        int[] res = new int[k];
        // iterate from the back because in the heap, the smallest one is at the beginning
        for (int i = k - 1; i >= 0; i--) {
            res[i] = heap.poll();
        }
        return res;
    }