Java Solution Easy to understand 18ms


  • 0
    V

    public class Solution {

    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;
    }
    

    }

    class MyEntryCompare implements Comparator<MyEntry> {

    @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;
    }
    

    }


  • 0
    E

    Arrays.sort(nums) give us O(n log n) running time


  • 0
    K

    Yes, sort takes O(nlogn).
    it doesn't satisfy the requirement


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.