Skip to content

347. Top K Frequent Elements

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
  • -104 <= nums[i] <= 104
  • 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.

Solution:

Top K -> heap

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] result = new int[k];

        // Step 1: Frequency map to count occurrences of each number
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        // O(n)


        // Step 2: Priority queue (min heap) based on frequency
        // Method 1 to write PriorityQueue
        // PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
        //     (a, b) -> a.getValue() - b.getValue()
        // );

        // // Method 2 to write PriorityQueue
        // PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
        //     new Comparator<Map.Entry<Integer, Integer>>(){
        //         @Override
        //         public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b){
        //             return a.getValue().compareTo(b.getValue());
        //         }
        //     }
        // );


        // My current Level is here; Practice more !!!
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            new Comparator<Map.Entry<Integer, Integer>>(){
                @Override
                public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b){
                    if (a.getValue() == b.getValue()){
                        return 0;
                    }else if (a.getValue() < b.getValue()){
                        return -1;
                    }else{
                        return 1;
                    }
                }
            }
        );



        // Step 3: Keep only the k most frequent elements in the heap
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){ //  O(n)
            pq.offer(entry); // logk
            if (pq.size() > k){
                pq.poll();
            }
        }
        // O(nlogk)




        // return in any order
        for (int i = 0; i < k; i++){
            result[i] = pq.poll().getKey();
        }

        // O(k)

        return result;

    }
}

// TC: O(nlogk)
// SC: O(n+k) -> n for map k for priorityqueue

PriorityQueue 需要加强熟悉.

map.entrySet()

pq.poll().getKey()