85% Heap and hashmap solution, without using set or map


  • 0
    M

    I admit it's not n*logk, but it's much faster than black red tree, even when compiling with -O0

    template <typename K, typename V>
    class priority_hashmap {
    public:
        unordered_map<K, int> ktol;
        typedef pair<K,V> KV;
        vector<KV> que;
        function<bool(KV const&, KV const&)> comp;
        priority_hashmap(function<bool(KV const&, KV const&)> &&comp):comp(comp) {
            que.push_back(KV());
        };
        priority_hashmap(function<bool(KV const&, KV const&)> const& comp):comp(comp) {
            que.push_back(KV());
        };
        
        V getv(K const& k) {
            if (ktol.find(k) == ktol.end()) return V();
            return que[ktol[k]].second;
        }
        
        void update(K const& k, V const& v) {
            if (ktol.find(k) == ktol.end()) {
                ktol[k] = que.size();
                que.push_back({k,v});
            } else {
                que[ktol[k]].second = move(v);
            }
            
            adjust(ktol[k]);
        }
        
        void del(K const& k) {
            int l = ktol[k];
            qswap(l, que.size()-1);
            K const& backk = que.back().first;
            ktol.erase(backk);
            que.pop_back();
            if (l < que.size())
                adjust(l);
        }
        
        void pop(KV &kv) {
            if (que.size() == 1) return;
            kv = que[1];
            qswap(1, que.size()-1);
            del(kv.first);
            adjust(1);
        }
        
        V const& top() const {
            return que[1];
        }
    
    private:
        
        void adjust(int l) {
            int nl = l;
            while (nl > 1) {
                int pl = (nl>>1);
                if (comp(que[nl], que[pl])) {
                    qswap(nl, pl);
                    nl = pl;
                } else {
                    break;
                }
            }
            
            if (nl < l) return;
            nl = (l<<1);
            while (nl < que.size()) {
                int s = l;
                if (comp(que[nl], que[s])) s = nl;
                if (nl+1 < que.size() && comp(que[nl+1], que[s])) s = nl+1;
                if (l != s) {
                    qswap(l, s); 
                    l = s; nl = (l<<1);
                } else break;
            }
        }
        
        void qswap(int a, int b) {
            if (a == b) return;
            K const& ka = que[a].first;
            K const& kb = que[b].first;
            swap(ktol[ka], ktol[kb]);
            swap(que[a], que[b]);
        }
    };
    class Solution {
    public:
    
        
        vector<string> topKFrequent(vector<string>& words, int k) {
            typedef pair<string, int> KV;
            priority_hashmap<string, int> pm([](KV const& a, KV const& b)->bool{
                if (a.second == b.second) return a.first < b.first;
                return a.second > b.second;
            });
            vector<string> ret;
            unordered_map<string, int> dcnt;
            for (auto &w : words) {
                dcnt[w]++;
            }
            for (auto &kv : dcnt) {
                pm.update(kv.first, kv.second);
            }
            
            KV tmp;
            for (int i = 0; i < k; i++) {
                pm.pop(tmp);
                ret.push_back(tmp.first);
            }
            return ret;
        }
    };
    

Log in to reply
 

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