Top K Frequent Elements(Medium)

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

class MyEntryCompare implements Comparator {

@Override
public int compare(MyEntry o1, MyEntry o2) {
    if (o1.value > o2.value) return -1;
    return 1;
}
}

class MyEntry { Integer key; Integer value;

public MyEntry(int key, int value) {
    this.key = key;
    this.value = value;
}
}

public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> rst = new ArrayList<>();
    PriorityQueue<MyEntry> priorityQueue = new PriorityQueue<>(new MyEntryCompare());
    if (nums == null || nums.length == 0) return rst;
    Arrays.sort(nums);
    int count = 1;
    for (int i = 1; i < nums.length; i++) {

        if (nums[i] != nums[i - 1]) {
            priorityQueue.offer(new MyEntry(nums[i - 1], count));
            count = 1;
        } else {
            count++;
        }
    }
    priorityQueue.offer(new MyEntry(nums[nums.length - 1], count));

    int size =priorityQueue.size();
    for (int i = 0; i < k && i < size; i++) {
        rst.add(priorityQueue.poll().key);
    }

    return rst;
}