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

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()

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

*/