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:

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // pq
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        for (Map.Entry<Integer, Integer> e : map.entrySet()){
            pq.offer(e);
        }

        int[] result = new int[k];

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

        return result;



    }
}


// TC: O(nlogn)
// SC: O(n)

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()

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // pq
        // PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));

        // Map<Integer, Integer> map = new HashMap<>();

        // for (int i = 0; i < nums.length; i++){
        //     map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        // }

        // for (Map.Entry<Integer, Integer> e : map.entrySet()){
        //     pq.offer(e);
        // }

        // int[] result = new int[k];

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

        // return result;

        return Arrays.stream(nums)
            .boxed()
            .collect(Collectors.groupingBy(
                n -> n,
                Collectors.counting()
            ))
            .entrySet()
            .stream()
            .sorted((a, b) -> Long.compare(b.getValue(), a.getValue()))
            .limit(k)
            .map(Map.Entry::getKey)
            .mapToInt(Integer::intValue)
            .toArray();
    }
}


// TC: O(nlogn)
// SC: O(n)