347 Top K Frequent Elements

347. Top K Frequent Elements

1. Question

Given a non-empty array of integers, return thekmost 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(nlogn), where n is the array's size.

2. Implementation

(1) Bucket Sort

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();

        if (nums.length == 0 || k <= 0) {
            return res;
        }

        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] bucket = new List[nums.length + 1];

        for (int key : map.keySet()) {
            int freq = map.get(key);

            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }

        for (int i = nums.length; i >= 0 && res.size() < k; i--) {
            if (bucket[i] != null) {
                res.addAll(bucket[i]);
            }
        }
        return res;
    }
}

(2) Heap

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return res;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<NumInfo> minHeap = new PriorityQueue<>();

        for (int key : map.keySet()) {
            minHeap.add(new NumInfo(key, map.get(key)));

            if (minHeap.size() > k) {
                minHeap.remove();
            }
        }

        while (!minHeap.isEmpty()) {
            res.add(0, minHeap.remove().val);
        }
        return res;
    }

    class NumInfo implements Comparable<NumInfo> {
        int val;
        int freq;

        public NumInfo(int val, int freq) {
            this.val = val;
            this.freq = freq;
        }

        public int compareTo(NumInfo that) {
            return this.freq - that.freq;
        }
    }
}

3. Time & Space Complexity

Bucket Sort: 时间复杂度O(n), 空间复杂度O(n)

Heap: 时间复杂度O(n + nlogk), 空间复杂度O(n)