Top k Frequent Words (Ladder)

Description

Given a list of words and an integer k, return the top k frequent words in the list.

Notice You should order the words by the frequency of them in the return list, the most frequent one comes first. If two words has the same frequency, the one with lower alphabetical order come first.

Example

Given
[
    "yes", "lint", "code",
    "yes", "code", "baby",
    "you", "baby", "chrome",
    "safari", "lint", "code",
    "body", "lint", "code"
]
for k = 3, return ["code", "lint", "baby"].
for k = 4, return ["code", "lint", "baby", "yes"],

Challenge
Do it in O(nlogk) time and O(n) extra space.
Extra points if you can do it in O(n) time with O(k) extra space approximation algorithms.

Link

Lintcode_ladder

Method

1. minheap, O(nlogk) S(k)
2. x

Example

1. 1

   class Node {
   public:
    string s;
    int freq;
    //int lastseen;
    Node() {}
    Node(string _s, int _freq): s(_s), freq(_freq) {}
   };
   class CompNode {
   public:
    // For minheap, top is samllest, 
    // return true when left > right, left(large) shiftdown
    // small will shiftup
    // large will shiftdown
    // Similar to greater<T> 
    //
    // For maxheap, top is largest, 
    // return true when left < right, left(small) shiftdown
    // large will shiftup
    // small will shiftdown
    bool operator()(Node& left, Node& right) const {
        // keep alphabetical order
        // e.g: a  b c d....
        // for minheap, make left shiftdown when left is in smaller abc.. order
        if (left.freq == right.freq) {
            return left.s < right.s;
        }
        // for minheap, make the left shiftdown when left is larger
        return left.freq > right.freq;
    }  
   };
   class Solution {
   public:
    /**
     * @param words an array of string
     * @param k an integer
     * @return an array of string
     */
    vector<string> topKFrequentWords(vector<string>& words, int k) {
        // Write your code here
        if (words.empty()) {
            return {};
        }
        vector<string> result;
        unordered_map<string, Node> dict;
        priority_queue<Node, vector<Node>, CompNode> minheap;
        int n = words.size();
        // record freq
        for (int i = 0; i < n; ++i) {
            if (dict.find(words[i]) != dict.end()) {
                dict[words[i]].freq++;
            } else {
                dict[words[i]].freq = 1;
            }
        }
        // push to heap
        for (auto& i : dict) {
            if (minheap.size() < k) {
                minheap.push(Node(i.first, i.second.freq));
            } else {
                minheap.push(Node(i.first, i.second.freq));
                minheap.pop();
            }
        }
        // get top k freq
        while (!minheap.empty()) {
            Node cur = minheap.top();
            minheap.pop();
            result.push_back(cur.s);
        }
        reverse(result.begin(), result.end());
        return result;
    }
   };
   

Similar problems

x

Tags

x