# 347    Top K Frequent Elements

## 347. [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/description/)

## 1. Question

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(nlogn), where n is the array's size.

## 2. Implementation

**(1) Bucket Sort**

```java
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**

```java
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)