O(nlogn) time using priority queue and O(n) time using bucket sort (C++)


  • 0
    F
    // (1) use a priority queue to find top K frequent words.
    //     O(n log k) time - use priority queue with O(n) space
        struct cmp{
          bool operator()(const pair<int,string> a, const pair<int,string> b){
              if( a.first != b.first) return a.first > b.first; // number sorted from small to large
              else{
                  return a.second < b.second; // string sorted with the higher alphabetical order comes first.
              }
          }  
        };
        vector<string> topKFrequent(vector<string>& words, int k) {
            if( words.size() == 0) return vector<string>();
            
            unordered_map<string, int> freq;
            for(auto s : words) freq[s]++;
            
            priority_queue<pair<int,string>, vector<pair<int,string>>, cmp> pq;
            for(auto it = freq.begin(); it != freq.end(); it++){
                pq.push(make_pair(it->second, it->first));
                if(pq.size() > k ) pq.pop();
            }
            
            vector<string> res;
            for(int i = 0; i < k; i++){
                res.insert(res.begin(), pq.top().second); 
                pq.pop();
            }
            return res;
        }
    
    
    
     // solution 2: using bucket sort with O (n ) time
        vector<string> topKFrequent(vector<string>& words, int k) {
            if( words.size() == 0) return vector<string>();
            
            unordered_map<string, int> freq;
            for(auto s : words) freq[s]++;
            
            vector<set<string>> bucket(words.size(), set<string>());
            for(auto it = freq.begin(); it != freq.end(); it++){
                bucket[it->second].insert(it->first);
            }
            
            vector<string> res;
            bool findK = false;
            for(int i = bucket.size() - 1; i >= 0; i--){
                if(bucket[i].size() > 0 ){
                    for(auto e : bucket[i]){
                        res.push_back(e);
                        if(res.size() == k ){
                            findK = true;
                            break;
                        }
                    }
                    if( findK ) break;
                }
            }
            return res;
        }
    

  • 0

    @fancy1984

    Your bucket solution is not O(n)


Log in to reply
 

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