Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

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.

• It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.

• You can return the answer in any order.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums)
            map.put(x, map.getOrDefault(x, 0) + 1);
        ArrayList<Integer>[] list = new ArrayList[nums.length + 1];
        for (int x : map.keySet()) {
            if (list[map.get(x)] == null)
                list[map.get(x)] = new ArrayList<>();
            list[map.get(x)].add(x);
        }
        int[] ans = new int[k];
        int index = 0;
        for (int i = list.length - 1; i >= 0 && k > 0; i--) {
            if (list[i] != null) {
                for (int j = 0; k > 0 && j < list[i].size(); j++) {
                    ans[index++] = list[i].get(j);
                    k--;
                }
                if (k == 0)
                    break;
            }
        }
        return ans;
    }
}