C++에서 자주 사용되는 K 단어

비어 있지 않은 단어 목록이 있다고 가정합니다. k개의 가장 빈번한 요소를 찾아야 합니다. 우리의 대답은 가장 높은 빈도에서 가장 낮은 빈도로 정렬되어야 합니다. 두 단어의 빈도가 같으면 알파벳 순서가 낮은 단어가 먼저 배치됩니다. 따라서 배열이 ['', 'sky', 'is', 'blue', 'the', 'weather', 'is', 'comfortable']인 경우 가장 자주 사용되는 단어는 ["is", "그","파란색"]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• m이라는 하나의 지도 정의
• 하나의 우선 순위 대기열 생성 v
• for i :=0에서 n, 여기서 n은 단어 배열의 크기입니다. 그런 다음 m[words[i]]를 1만큼 증가
• map
  의 각 요소 e에 대해
  • v의 크기가
  • 그렇지 않고 v.top의 값이
  • 그렇지 않고 v.top의 값이 e의 값이고 v.top의 키가 e의 키인 경우 v에서 최상위 요소를 삭제하고 v에 e를 삽입합니다.
• res라는 하나의 배열 정의
• v가 비어 있지 않은 동안
  • temp :=v의 상단
  • v에서 상단 삭제
  • res 배열에 temp 키 삽입
• res 배열 반전
• 반환 결과

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
struct Comparator{
   bool operator()(pair <string ,int> a, pair <string, int> b){
      if(a.second != b.second) return !(a.second < b.second);
         return !(a.first > b.first);
   }
};
class Solution {
public:
   static bool cmp(pair <string, int> a, pair <string, int> b){
      if(a.second != b.second) return a.second > b.second;;
         return a.first < b.first;
   }
   vector<string> topKFrequent(vector<string>& words, int k) {
      map<string, int> m;
      priority_queue < pair <string, int>, vector < pair <string, int> >, Comparator > v;
      for(int i = 0; i < words.size(); i++){
         m[words[i]]++;
      }
      map<string, int> :: iterator i = m.begin();
      while(i != m.end()){
         if(v.size() < k){
            v.push(*i);
         }
         else if(v.top().second < i->second){
            v.pop();
            v.push(*i);
         }
         else if(v.top().second == i->second && v.top().first > i->first){
            v.pop();
            v.push(*i);
         }
         i++;
      }
      vector <string> res;
      while(!v.empty()){
         pair <string, int> temp = v.top();
         v.pop();
         res.push_back(temp.first);
      }
      reverse(res.begin(), res.end());
      return res;
   }
};
main(){
   Solution ob;
   vector<string> v = {"the", "sky", "is", "blue", "the", "weather", "is", "comfortable"};
   print_vector(ob.topKFrequent(v, 3));
}

입력

["the", "sky", "is", "blue", "the", "weather", "is", "comfortable"]
3

출력

["is","the","blue"]