TopK

TopK problem , Whether it's asking for the front K Big / front K Small / The first K Big / The first K Wait a minute , There are the following ways ：

1. O(N)： It is the most efficient way to solve TopK problem

2. O(NlogK)： Big root pile （ front K Small ）/ Heap （ front K Big ）

3. O(NlogK)： Binary search tree

4. O(N): In the case of limited data range , You can count and sort directly O(N) Efficient solution

347. front K High frequency elements

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 .
Answer key ：
1）Hashmap
use map Record the number of occurrences of the element , Find the number of occurrences of the most frequent element , Add to the result array according to the number of occurrences

2) Pile up
As above, record the number of occurrences , Form an array of occurrences , Find its front k Big . Build a small top heap to traverse . If the number of elements in the heap is less than k, You can insert it directly into the heap .
If the number of elements in the heap is equal to k, Then check the size of the heap top and the current occurrence times . If the top of the pile is larger , It means at least k The number of occurrences is greater than the current value , Therefore, the current value is discarded ; otherwise , Just pop out of the top of the pile , Insert the current value into the heap . After traversal , The elements in the heap represent 「 Number of occurrences array 」 Middle front k Big value

solution：
1）

class Solution {
    
    public int[] topKFrequent(int[] nums, int k) {
    
        int res[]=new int[k];
        Map<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 maxTimes=0;
         for(Map.Entry<Integer, Integer> entry : map.entrySet()){
    
            if(entry.getValue() > maxTimes){
    
                maxTimes = entry.getValue();
            }
        }
        while(k > 0){
    
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
    
                if(entry.getValue() == maxTimes){
    
                    res[k - 1] = entry.getKey();
                    k--;
                }
            }
            maxTimes--;
        }

        return res;
    }
}
       

2）

class Solution {
    
    public int[] topKFrequent(int[] nums, int k) {
    
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
    
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[]  The first element of represents the value of the array , The second element represents the number of times the value appears 
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
    
            public int compare(int[] m, int[] n) {
    
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
    
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
    
                if (queue.peek()[1] < count) {
    
                    queue.poll();
                    queue.offer(new int[]{
    num, count});
                }
            } else {
    
                queue.offer(new int[]{
    num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
    
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

Map yes java The interface ,Map.Entry yes Map An internal interface for .

Map Provides some common methods , Such as keySet()、entrySet() Other methods .

keySet() Method return value is Map in key Collection of values ;entrySet() The return value of also returns a Set aggregate , The type of this collection is Map.Entry.

Map.Entry yes Map An internal interface for declarations , This interface is generic , Defined as Entry<K,V>. It said Map One of the entities in （ One key-value Yes ）. There are getKey(),getValue Other methods