Max-heap O(N + Nlog(N) + Klog(N)) and Min-Heap O(N + (N-K)log(K) + KlogK) method


  • 0
    S
    class Solution {
        typedef pair<int, int> PAIR;
        struct ComparisonClass {
            bool operator() (const PAIR &lhs, const PAIR &rhs) {
               return lhs.second < rhs.second;
            };
        };
        
        struct ComparisonClassMin {
            bool operator() (const PAIR &lhs, const PAIR &rhs) {
               return lhs.second > rhs.second;
            };
        };
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            
            map<int,int> hash;
            for (int i = 0; i< nums.size(); ++i) {
                if (hash.find(nums[i]) != hash.end()) {
                    hash[nums[i]]+=1;
                } else {
                    hash[nums[i]] =1;
                }
            }
            /* // This is Max heap method. Created Max heap of top number and extracted K items from the heap. 
            // Complexity is O(N + Nlog(N)). O(N) for creation of heap. O(Klog(N)) for extracting K elements from heap. 
            // Overall complexity O(N + Nlog(N) + O(Klog(N)))
            priority_queue< PAIR, vector<PAIR>, ComparisonClass> pq(hash.begin(), hash.end());
            vector<int> out;
            for (int i = 0; i<k;++i) {
                out.push_back(pq.top().first);
                pq.pop();
            }
            return out;*/
            
            // The Other method is min-heap method. ,Where we create Min-Heap for K elements 
            // For rest of the elements if root of heap is smaller than every further element. Remove root and insert the element. 
            // The remaining items in the heap are Top elements. 
            // O(K) for creating heap. O(N-K(logK)) for inserting remaining N-K elements. O(KLogK) for extracting all K elements
            // Overall Complexity O(K + (N-K)log(K) + KlogK) this is significantly less than above method. 
           
            
            priority_queue< PAIR, vector<PAIR>, ComparisonClassMin> pq;
            
            map<int,int>::iterator start = hash.begin();
            map<int,int>::iterator end = hash.end();
            int i = 0;
            while(start != end) {
                if (i < k) {
                    pq.push(make_pair(start->first,start->second));
                } else {
                    if (pq.top().second < start->second) {
                        pq.pop();
                        pq.push(make_pair(start->first,start->second));
                    }
                }
                ++i;
                ++start;
            }
            vector<int> out;
            while(!pq.empty()) {
                out.push_back(pq.top().first);
                pq.pop();
            }
            reverse(out.begin(), out.end());
            return out;
        }
    };
    

    Code along with explanation


Log in to reply
 

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