C++實現LeetCode(692.前K個高頻詞)

Posted on by

[LeetCode] 692.Top K Frequent Words 前K個高頻詞

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
Output: [“i”, “love”]
Explanation: “i” and “love” are the two most frequent words.
Note that “i” comes before “love” due to a lower alphabetical order.

Example 2:

Input: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
Output: [“the”, “is”, “sunny”, “day”]
Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words,
with the number of occurrence being 4, 3, 2 and 1 respectively.

Note:

  1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  2. Input words contain only lowercase letters.

Follow up:

  1. Try to solve it in O(n log k) time and O(n) extra space.
  2. Can you solve it in O(n) time with only O(k) extra space?

這道題讓我們求前K個高頻詞，跟之前那道題 Top K Frequent Elements 極其類似，換瞭個數據類型就又是一道新題。唯一的不同就是之前那道題對於出現頻率相同的數字，沒有順序要求。而這道題對於出現頻率相同的單詞，需要按照字母順序來排。但是解法都一樣，還是用最小堆和桶排序的方法。首先來看最小堆的方法，思路是先建立每個單詞和其出現次數之間的映射，然後把單詞和頻率的pair放進最小堆，如果沒有相同頻率的單詞排序要求，我們完全可以讓頻率當作pair的第一項，這樣priority_queue默認是以pair的第一項為key進行從大到小的排序，而當第一項相等時，又會以第二項由大到小進行排序，這樣第一項的排序方式就與題目要求的相同頻率的單詞要按字母順序排列不相符，當然我們可以在存入結果res時對相同頻率的詞進行重新排序處理，也可以對priority_queue的排序機制進行自定義，這裡我們采用第二種方法，我們自定義排序機制，我們讓a.second > b.second，讓小頻率的詞在第一位，然後當a.second == b.second時，我們讓a.first < b.first，這是讓字母順序大的排在前面（這裡博主需要強調一點的是，priority_queue的排序機制的寫法和vector的sort的排序機制的寫法正好順序相反，同樣的寫法，用在sort裡面就是頻率小的在前面，不信的話可以自己試一下）。定義好最小堆後，我們首先統計單詞的出現頻率，然後組成pair排序最小堆之中，我們隻保存k個pair，超過瞭就把隊首的pair移除隊列，最後我們把單詞放入結果res中即可，參見代碼如下：

解法一：

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res(k);
        unordered_map<string, int> freq;
        auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp) > q(cmp);
        for (auto word : words) ++freq[word];
        for (auto f : freq) {
            q.push(f);
            if (q.size() > k) q.pop();
        }
        for (int i = res.size() - 1; i >= 0; --i) {
            res[i] = q.top().first; q.pop();
        }
        return res;
    }
};

下面這種解法還是一種堆排序的思路，這裡我們用map，來建立次數和出現該次數所有單詞的集合set之間的映射，這裡也利用瞭set能自動排序的特性，當然我們還是需要首先建立每個單詞和其出現次數的映射，然後將其組成pair放入map種，map是從小到大排序的，這樣我們從最後面取pair，就是次數最大的，每次取出一層中所有的單詞，如果此時的k大於該層的單詞個數，就將整層的單詞加入結果res中，否則就取前K個就行瞭，取完要更更新K值，如果K小於等於0瞭，就break掉，返回結果res即可，參見代碼如下：

解法二：

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res;
        unordered_map<string, int> freq;
        map<int, set<string>> m;
        for (string word : words) ++freq[word];
        for (auto a : freq) {
            m[a.second].insert(a.first);
        }
        for (auto it = m.rbegin(); it != m.rend(); ++it) {
            if (k <= 0) break;
            auto t = it->second;
            vector<string> v(t.begin(), t.end());
            if (k >= t.size()) {
                res.insert(res.end(), v.begin(), v.end());
            } else {
                res.insert(res.end(), v.begin(), v.begin() + k);
            }
            k -= t.size();
        }
        return res;
    }
};

下面這種解法是一種桶排序的思路，我們根據出現次數建立多個bucket，桶的個數不會超過單詞的個數，在每個桶中，我們對單詞按字符順序進行排序。我們可以用個數組來表示桶，每一層中放一個集合，利用set的自動排序的功能，使其能按字母順序排列。我們還是需要首先建立每個單詞和其出現次數的映射，然後將其組成pair放入map種，map是從小到大排序的，這樣我們倒序遍歷所有的桶，這樣取pair，就是次數最大的，每次取出一層中所有的單詞，如果此時的k大於該層的單詞個數，就將整層的單詞加入結果res中，否則就取前K個就行瞭，取完要更更新K值，如果K小於等於0瞭，就break掉，返回結果res即可，參見代碼如下：

解法三：

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res;
        unordered_map<string, int> freq;
        vector<set<string>> v(words.size() + 1, set<string>());
        for (string word : words) ++freq[word];
        for (auto a : freq) {
            v[a.second].insert(a.first);
        }
        for (int i = v.size() - 1; i >= 0; --i) {
            if (k <= 0) break;
            vector<string> t(v[i].begin(), v[i].end());
            if (k >= t.size()) {
                res.insert(res.end(), t.begin(), t.end());
            } else {
                res.insert(res.end(), t.begin(), t.begin() + k);
            }
            k -= t.size();
        }
        return res;
    }
};

類似題目：

Top K Frequent Elements

Design Search Autocomplete System

參考資料：

https://discuss.leetcode.com/topic/106861/o-nlog-k-priority-queue-c-code 

https://discuss.leetcode.com/topic/106868/clean-heap-based-solution-o-nlogk-time-and-o-n-space-16ms

到此這篇關於C++實現LeetCode(692.前K個高頻詞)的文章就介紹到這瞭,更多相關C++實現前K個高頻詞內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：