# 0347. Top K Frequent Elements

<https://leetcode.com/problems/top-k-frequent-elements>

## Description

Given an integer array `nums` and an integer `k`, return *the* `k` *most frequent elements*. You may return the answer in **any order**.

**Example 1:**

```
**Input:** nums = [1,1,1,2,2,3], k = 2
**Output:** [1,2]
```

**Example 2:**

```
**Input:** nums = [1], k = 1
**Output:** [1]
```

**Constraints:**

* `1 <= nums.length <= 105`
* `k` is in the range `[1, the number of unique elements in the array]`.
* It is **guaranteed** that the answer is **unique**.

**Follow up:** Your algorithm's time complexity must be better than `O(n log n)`, where n is the array's size.

## ac1: bucket sort

```java
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<Integer>();
        // edge cases
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) return res;

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

        // buckets
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : map.keySet()) {
            int frequency = map.get(key);
            if (buckets[frequency] == null) buckets[frequency] = new ArrayList<Integer>();
            buckets[frequency].add(key);
        }

        for (int i = buckets.length - 1; i >= 0 && res.size() < k; i--) {
            if (buckets[i] == null) continue;  // no val in this frequency
            res.addAll(buckets[i]);
        }

        return res;
    }
}

/*
1. bucket sort, best, O(n) time, O(2n) space
2. maxHeap, O(nlogk) time, O(k+n)space

*/
```

## ac2: minHeap

notice about: `Map.Entry<>`, `map.entrySet()`, `entry.getKey()`, `entry.getValue()`

```java
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<Integer>();
        // edge cases
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) return res;

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

        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> {return a.getValue() - b.getValue();});
        for (Map.Entry<Integer, Integer> me : map.entrySet()) {
            pq.add(me);
            if (pq.size() > k) pq.poll();  // remove minimun one
        }

        while (!pq.isEmpty()) {
            res.add(pq.poll().getKey());
        }

        return res;
    }
}

/*
1. bucket sort, best, O(n) time, O(2n) space
2. maxHeap, O(nlogk) time, O(k+n)space

*/
```