題目

---

思路

通過統計字符串的出現次數，并根據出現次數和字典序對字符串進行排序，找出出現頻率最高的前k個字符串。使用一個自定義的仿函數作為排序的比較函數，通過map容器進行統計，然后將結果存儲在向量中返回

---

代碼

 //仿函數struct kvCom{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second>p2.second || (p1.second==p2.second && p1.first<p2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> CountMap ;for (auto &e : words){CountMap[e]++;}//sort中的支持的是隨機迭代器，而map是雙向迭代器，所有將map中的數據存到vector中再用sortvector<pair<string,int>> sortV(CountMap.begin(),CountMap.end());//穩定的sort//stable_sort(sortV.begin(),sortV.end(),kvCom());sort(sortV.begin(),sortV.end(),kvCom());//對次數排序vector<string> ret;for (int i=0;i<k;i++){ret.push_back(sortV[i].first);}return ret;}

代碼講解

 struct kvCom{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second>p2.second || (p1.second==p2.second && p1.first<p2.first);}};

• struct kvCom：定義了一個結構體kvCom，它是一個仿函數（function object）。仿函數是重載了函數調用操作符operator()的對象，可以像函數一樣被調用。在這個結構體中，重載了operator()，用于定義對存儲字符串-整數對的pair進行比較的規則。
• bool operator()(const pair<string,int>& p1,const pair<string,int>& p2)：這是kvCom結構體中的函數調用操作符的重載。它接受兩個參數，都是pair<string,int>類型的引用。函數的目的是比較這兩個pair對象的大小，返回一個布爾值表示兩個對象的大小關系。具體的比較規則如下：
  首先比較第二個元素（即整數部分）的大小，如果p1的第二個元素大于p2的第二個元素，則返回true，否則返回false。
  如果兩個元素的第二個元素相等，那么比較第一個元素（即字符串部分）的大小，如果p1的第一個元素小于p2的第一個元素，則返回true，否則返回false。

vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> CountMap ;for (auto &e : words){CountMap[e]++;}//sort中的支持的是隨機迭代器，而map是雙向迭代器，所有將map中的數據存到vector中再用sortvector<pair<string,int>> sortV(CountMap.begin(),CountMap.end());//穩定的sort//stable_sort(sortV.begin(),sortV.end(),kvCom());sort(sortV.begin(),sortV.end(),kvCom());//對次數排序vector<string> ret;for (int i=0;i<k;i++){ret.push_back(sortV[i].first);}return ret;}

• map<string,int> CountMap：定義了一個map容器CountMap，用于統計每個字符串在words中出現的次數。map是一個關聯容器，它存儲了鍵-值對，其中鍵是唯一的，即每個字符串只會在map中出現一次，值表示字符串出現的次數。

• for (auto &e : words)：遍歷words中的每個字符串，使用引用&e來獲取字符串的引用。這樣可以避免在循環中對字符串進行拷貝，提高性能。

• CountMap[e]++：將當前遍歷到的字符串e作為鍵，在CountMap中查找對應的值，并將其加1。如果e在CountMap中不存在，則會自動插入一個鍵為e，值為0的鍵-值對，然后將值加1。

• vector<pair<string,int>> sortV(CountMap.begin(),CountMap.end())：sort中的支持的是隨機迭代器，而map是雙向迭代器，所有將map中的數據存到vector中再用sort。使用CountMap中的數據初始化一個存儲字符串-整數對的sortV。這樣做是為了將CountMap中的數據按照出現次數進行排序。

• sort(sortV.begin(),sortV.end(),kvCom())：對sortV中的元素按照指定的排序規則進行排序。這里使用了kvCom結構體的對象作為比較函數，用來定義排序規則。排序的規則是按照字符串出現次數的降序排列，如果出現次數相同，則按照字符串的字典序（升序）進行排列。

• vector ret：定義一個字符串向量ret，用于存儲結果。

• for (int i=0;i<k;i++)：從排序后的向量sortV中取出前k個字符串。

• ret.push_back(sortV[i].first)：將第i個字符串的第一個元素（即字符串本身）添加到結果向量ret中。

• return ret：返回存儲了出現頻率最高的前k個字符串的向量ret。

（本題完）