C++ Unordered Map with Heap Sort k elements


  • 0
    T
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            if (nums.empty()) return vector<int>();
            
            unordered_map<int, int> map;
            for (int i=0; i < nums.size(); i++){
                map[nums[i]]++; //time appear of a number
            }
            
            vector<pair<int, int>> bucket;
            
            for ( auto it = map.begin(); it != map.end(); ++it ){
                bucket.push_back(make_pair(it->second, it->first));   //bucket contains all pairs of (frequency - number)  
            }
            
            //get the last k sorted in the list
            //sort the first k element with Heap Algo
            kth_element_sorted(bucket, k);
            
            vector<int> result;
            
            for (int i=0; i < k; i++){
                result.push_back(bucket[bucket.size()-1-i].second);
            }
            
            return result;
        }
        
        //Heap sort implementing...
        int left(int idx){
            return (idx << 1) + 1;
        }
        int right(int idx){
            return (idx << 1) + 2;
        }
        //maintain heap struct
        void max_heapify(vector<pair<int, int>>& bucket, int idx){
            int l = left(idx);
            int r = right(idx);
            int largest = idx;
            if (l < heap_size && bucket[l].first > bucket[largest].first) largest = l;
            if (r < heap_size && bucket[r].first > bucket[largest].first) largest = r;
            if (largest != idx){
                swap(bucket[largest], bucket[idx]);
                max_heapify(bucket, largest);
            }
        }
        //construct heap
        void construct_max_heap(vector<pair<int, int>>& bucket){
            heap_size = bucket.size();
            for (int i=heap_size<<1-1; i >= 0; i--) {
                max_heapify(bucket, i);
            }
        }
        
        //reorganize k element
        void kth_element_sorted(vector<pair<int, int>>& bucket, int k){
            construct_max_heap(bucket);
            for (int i=0; i < k; i++) {
                swap(bucket[heap_size-1], bucket[0]);
                heap_size--;
                max_heapify(bucket, 0);
            }
        }
        private:
            int heap_size;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.