C++ beats 92% using heap


  • 0
    W
    class Solution {
    public:
        static bool cmp(pair<int, int>& a, pair<int, int>& b) {
            return a.second > b.second;
        }
        
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> hashtbl;
            
            for (auto i : nums) {
                hashtbl[i]++;
            }
            
            vector<pair<int, int>> minHeap;
            make_heap(minHeap.begin(), minHeap.end(), cmp);
            
            for (auto r : hashtbl) {
                if (minHeap.size() < k) {
                    minHeap.push_back(make_pair(r.first, r.second));
                    push_heap(minHeap.begin(), minHeap.end(), cmp);
                } else {
                    if (minHeap.front().second < r.second) {
                        pop_heap(minHeap.begin(), minHeap.end(), cmp);
                        minHeap.back() = make_pair(r.first, r.second);
                        push_heap(minHeap.begin(), minHeap.end(), cmp);
                    }
                }
            }
            
            vector<int> result;
            for (auto i : minHeap) {
                result.push_back(i.first);
            }
            
            return result;
        }
    };
    

  • 0
    C
        unordered_map<int, int> umap;
        vector<int> result;
        int maxc=0;
        for(auto i:nums) {
            maxc=max(++umap[i], maxc);
        }
        //cout<<maxc<<endl;
        for(int i=maxc;i>0;i--) {
            for(auto it = umap.begin(); it!=umap.end(); ++it)
                if(it->second==i && (k>0)) {
                    result.push_back(it->first);
                    k-=1;
                }
        }
        return result;

  • 0
    X

    You can use priority queue as heap


Log in to reply
 

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