Leetcode skimming: stack and queue 06 (top k high-frequency elements)

347. front K High frequency elements

Force button topic link

Given a non empty array of integers , Before returning the frequency of occurrence k High element .

Example 1:

• Input : nums = [1,1,1,2,2,3], k = 2
• Output : [1,2]

Example 2:

• Input : nums = [1], k = 1
• Output : [1]

Tips ：

• You can assume that given k Always reasonable , And 1 ≤ k ≤ The number of different elements in the array .
• The time complexity of your algorithm must be better than $O(n\log n)$ , n Is the size of the array .
• The question data guarantee the unique answer , let me put it another way , Before array k The set of high-frequency elements is unique .
• You can return the answers in any order .

It's another medium-sized problem, and one hit the soul , Gone with the wind hhhhh
Ideas ：
The hash table calculates the number of occurrences of each number
key 、 Values are put into two arrays , Sort by value , Key image synchronous transformation position
Return to the former K A digital .

package com.programmercarl.stacks_queues;
import java.util.HashMap;

/** * @ClassName TopKFrequent * @Descriotion TODO * @Author nitaotao * @Date 2022/6/30 14:13 * @Version 1.0 * https://leetcode.cn/problems/top-k-frequent-elements/ * 347.  front  K  High frequency elements  **/
public class TopKFrequent {
    
    public static int[] topKFrequent(int[] nums, int k) {
    
        /** *  Ideas ： *  Hash table count  */
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
    
            if (map.containsKey(nums[i])) {
    
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
    
                map.put(nums[i], 1);
            }
        }
        int[] keys = new int[map.size()];
        int[] values = new int[map.size()];
        int index = 0;
        for (Integer key : map.keySet()) {
    
            keys[index] = key;
            values[index] = map.get(key);
            index++;
        }
        //value  Sort ,key  Image synchronization Exchange  
        for (int i = 0; i < values.length-1; i++) {
    
            for (int j = i+1; j < values.length; j++) {
    
                if (values[i] < values[j]) {
    
                    int tempValue = values[i];
                    values[i] = values[j];
                    values[j] = tempValue;

                    int tempKey = keys[i];
                    keys[i] = keys[j];
                    keys[j] = tempKey;
                }
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
    
            result[i] = keys[i];
        }
        return result;
    }
}

There is another way to look at the solution , It's the train of thought that our teacher said in class before , Big top pile idea .

    public static int[] topKFrequent(int[] nums, int k) {
    
        /** *  Ideas ： *  Hash table count  */
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
    
            if (map.containsKey(nums[i])) {
    
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
    
                map.put(nums[i], 1);
            }
        }
        // Big top pile idea 
        // Priority queue , Sort by value size 
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
        for(Map.Entry<Integer,Integer>entry : map.entrySet()) {
    
            queue.offer(entry);
            // Before retention only k Number 
            if (queue.size() > k) {
    
                queue.poll();
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
    
            result[i] = queue.poll().getKey();
        }
        return result;
    }