347 Top K Frequent Elements

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

class Solution {
    class Counter {
        int frequency;
        int num;
        public Counter(int num, int frequency) {
            this.num = num;
            this.frequency = frequency;
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        Arrays.sort(nums);
        PriorityQueue<Counter> queue = new PriorityQueue<Counter>((a,b) -> (b.frequency-a.frequency));
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) count++;
            else {
                queue.add(new Counter(nums[i-1], count));
                count = 1;
            }
        }
        queue.add(new Counter(nums[nums.length-1], count));

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i ++) {
            result.add(queue.poll().num);
        }
        return result;
    }
}