C++程式：查詢序列中出現次數第二多的單詞

給定一個單詞陣列，我們需要找到頻率第二高的單詞。

讓我們假設一些簡單的輸入和輸出場景

假設我們有一個包含如下元素的陣列：[“point,” “world,” “articles,” “articles,” “articles,” “world,” “world,” “world,” “point”]。

單詞的頻率為：

“point”: 2
“world”: 4
“articles”: 3 // This will be the second most repeated word in the array.

因此，出現次數第二多的單詞是“articles”，我們的輸出是“articles”。

讓我們考慮另一種情況，其中陣列中有一組相似的單詞，例如[“abc”, “abc”, “abc”, “bab”, “bab”, “cat”]。序列中出現次數第二多的單詞將是“bab”。

“abc” = 3
“bab” = 2 // This will be the second most repeated word in the array.
“cat” = 1

我們可以使用雜湊表查詢給定單詞陣列中每個單詞的頻率，然後返回第二高的頻率。在C++中，我們可以使用`unordered_map`資料結構。

演算法

執行此任務需要遵循以下步驟：

  • 實現一個雜湊表。

  • 將向量中每個字串的頻率儲存在雜湊表中。

  • 在將每個字串儲存到雜湊表後遍歷雜湊表，以查詢具有第二高頻率的字串。

  • 然後，列印該字串作為輸出

示例

查詢列表中出現頻率第二高的單詞的C++實現如下：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
string solve(vector<string> words) {
   unordered_map<string, int> hash;
   for (auto word: words) {
      hash[word]++;
   }
   int first_max = INT32_MIN, sec_max = INT32_MIN;
   for (auto it: hash) {
      if (it.second > first_max) {
         sec_max = first_max;
         first_max = it.second;
      } else if (it.second > sec_max && it.second != first_max) {
         sec_max = it.second;
      }
   }
   for (auto it: hash) {
      if (it.second == sec_max) {
         return it.first;
      }
   }
   return "";
}
int main() {
   vector<string> words = { "point", "world", "articles", "articles", "articles", "world", "world", "world", "point" };
   cout << solve(words);
   return 0;
}

輸出

“articles”

結論

我們也可以在C++中使用`map`，但這沒有必要，因為我們不希望在雜湊時按字典順序對單詞進行排序。使用`map`也會比較昂貴，因為插入操作需要O(log(n))的時間複雜度，而`unordered_map`只需要O(1)。然而，對於更大的輸入，為了避免衝突並保持時間複雜度為O(1)，我們必須編寫自定義雜湊函式。

更新於：2022年8月10日

瀏覽量：313

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告
© . All rights reserved.