347. The first k high-frequency elements ●●

347. front K High frequency elements ●●

describe

Give you an array of integers nums And an integer k , Please return to the frequency before k High element . You can press In any order Return to the answer .

Example

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

Answer key

1. Hashtable + Two points （ Low efficiency ）

class Solution {
    
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        unordered_map<int, int> hashmap_num;		//  The hash table records the number of elements 
        unordered_map<int, int> hashmap_index;		//  The hash table records elements in ans Where the array appears 
        vector<int> ans;
        for(int i : nums){
    
            ++hashmap_num[i];
            if(hashmap_num[i] == 1){
    
                ans.emplace_back(i);				//  Insert the first occurrence of the element 
                hashmap_index[i] = ans.size()-1;
            }
            else{
    
                int l = 0;
                int r = ans.size()-1;
                while(l <= r){
    						//  Find the boundary position by dichotomy , Pay attention to judgment l<=r
                    int mid = l + (r-l)/2;			//  Pay attention to the following judgment  ans[mid] != i
                    if(hashmap_num[ans[mid]] > hashmap_num[i]-1 && ans[mid] != i){
    
                        l = mid + 1;        // l  The first is less than or equal to 
                    }else{
      
                        r = mid - 1;        // r  The last one is greater than 
                    }
                }
                swap(ans[l], ans[hashmap_index[i]]);		//  Exchange positions 
                swap(hashmap_index[ans[hashmap_index[i]]],hashmap_index[i]);	//  Index exchange 
            }
        }
        ans.resize(k);
        return ans;
    }
};

2. Hashtable

First statistics appear The most times n, Cycle decreases n Determine the hash table map.second = n The elements of , Until it fills up k individual .

• Time complexity ：$O(n\ast N)$,n Is the highest frequency ,N Number of values for different elements
• Spatial complexity ：$O(N)$

class Solution {
    
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        // first The corresponding element value second The number of occurrences of the corresponding element 
        unordered_map<int, int>hashmap;
        vector<int> ret;

        //  Record the number of occurrences of the element 
        for(int i : nums) hashmap[i]++;
        
        //  Find the highest frequency of element occurrence 
        int maxtimes = 0;   
        for (auto i : hashmap) {
    
            if (i.second > maxtimes) {
    
                maxtimes = i.second;
            }
        }
            
        //  Go from the highest to the lowest   Output... In sequence 
        while (k > 0){
    
            for (auto i : hashmap){
    
                if (i.second == maxtimes) {
    
                    ret.push_back(i.first);
                    k--;
                } 
            }
            maxtimes--;
        }
        return ret;
    }
};

3. The frequency of Heap sort

Create and maintain a size of k Small roots .

Overall time complexity $O(nlogk)$：

• Traversal statistics element frequency O(n)
• front k Number structure The scale is k The smallest pile minheap, O(k).
• Traversal scale k Other data , If it is larger than the top of the pile, it will be put into the pile , Sinking maintenance scale is k The smallest pile minheap. O(nlogk)
  ( If you need to output by frequency , Yes, the scale is k Sort the heap )

Handwritten heap data structure ：

class Solution {
    
public:
    void adjustHeap(vector<pair<int, int>>& heap, int idx, int k){
      //  Adjust to a small top pile 
        int child = 2 * idx + 1;
        while(child < k){
       
            if(child + 1 < k && heap[child+1].second < heap[child].second){
     
                ++child;                                            //  Select child nodes with less frequency 
            }
            if(heap[idx].second > heap[child].second){
                  //  Adjusting position 
                swap(heap[idx], heap[child]);
                idx = child;
                child = 2*idx+1;                                    //  Update the comparison node 
            }else{
    
                break;
            }
        }
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        unordered_map<int, int> hashmap;
        for(int num : nums) ++hashmap[num];     //  Statistics frequency 
        vector<pair<int, int>> heap(k);         //  The maintenance size is k The little top pile 
        int idx = 0;
        for(std::unordered_map<int, int>::iterator iter = hashmap.begin(); iter != hashmap.end(); ++iter){
    
            if(idx < k){
    
                heap[idx++] = *iter;            //  Before k Create a heap of elements 
            }else{
    
                break;
            }
        }
        for(int i = 2*k-1; i >= 0; --i){
    
            adjustHeap(heap, i, k);             //  Adjust the heap structure upward from the last non leaf node 
        }

        idx = 0;
        for(std::unordered_map<int, int>::iterator iter = hashmap.begin(); iter != hashmap.end(); ++iter){
    
            if(idx < k){
    
                ++idx;
            }else{
    
                if(iter->second > heap[0].second){
          //  Compare the subsequent nodes to update the heap structure 
                    heap[0] = *iter;
                    adjustHeap(heap, 0, k);
                }
            }
        }
        vector<int> ans;
        for(auto p : heap) ans.emplace_back(p.first);   //  Take out the contents of the heap 
        return ans;
    }
};

• Use the priority queue container priority_queue：

In priority queue , High priority elements are first out of the queue , Not according to the requirements of first in, first out , Like a heap (heap).

priority_queue<Type, Container, Functional>;
among Type Is the data type ,Container A container for storing data ,Functional It is the way of element comparison .
If the third parameter is used , The second parameter cannot be omitted .

Container Must be a container implemented in an array , such as vector, deque.
STL The default is vector, The default comparison method is operator < From small to large , That is, if the latter two parameters are defaulted , The priority queue is Big pile top , The team leader has the most elements .

Use greater<int> after , data From big to small array , The heap structure corresponds to Small cap pile ,top() The minimum value is returned instead of the maximum value ！

class Solution {
    
public:
     //  Small cap pile , Comparison function 
    class mycomparison {
    
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    
            return lhs.second > rhs.second; //  The result of exchanging the first order of the small top heap is   From big to small , therefore  > 
        } 
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        //  To count the frequency of elements 
        unordered_map<int, int> map; // map<nums[i], Corresponding number of occurrences >
        for (int i = 0; i < nums.size(); i++) {
    
            map[nums[i]]++;
        }

        //  Sort frequencies 
        //  Define a small top heap , The size is k, priority_queue<Type, Container, Functional>
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        //  Use a fixed size of k The little top pile , The value of all frequencies of the scanning surface 
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
    
            pri_que.push(*it);
            if (pri_que.size() > k) {
     //  If the size of the heap is larger than K, The queue pops up , Make sure the heap size is always k
                pri_que.pop();
            }
        }

        //  Before finding out K High frequency elements , Because the small top pile ejects first is the smallest , So output to the array in reverse order 
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
    
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};

4. The frequency of Bucket sort

Count the maximum frequency , Set the size to maxCnt Bucket set of .

//  Bucket sort ( Sort by frequency )
class Solution {
    
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
    
        unordered_map<int, int> countMap;
        int maxCount = 0;
        for (const int& x : nums) {
    
            maxCount = std::max(maxCount, ++countMap[x]);  	//  utilize map Count the frequency of each element , At the same time, the maximum frequency 
        }

        vector<vector<int>> buckets(maxCount + 1);  		//  The size of the bucket is maxCount+1 ( That is, the elements in the same bucket have the same frequency )
        for (const auto& pair : countMap) {
    
            buckets[pair.second].push_back(pair.first);  	//  according to map Frequency of each element recorded in   Put the elements into the corresponding bucket 
        }

        vector<int> result;
        for (int i = maxCount; i >= 0 && result.size() < k; --i) {
      //  from   The last bucket ( The highest frequency )  Traversing , Thus, the former k High frequency elements 
            for (const auto& x : buckets[i]) {
    
                result.push_back(x);
                if (result.size() == k) break;
            }
        }

        return result;
    }
};

5. The frequency of Quick sort