상위 K 자주 사용되는 단어


난이도 중급
자주 묻는 질문 Accolite Fourkites 인포시스
해싱 더미 시도

상위 K 개 단어 문제에서 우리는 단어 목록과 정수 k를 제공했습니다. 목록에서 가장 자주 사용되는 k 개의 문자열을 인쇄합니다.

상위 K 자주 사용되는 단어

입력 :

list = { "code", "sky", "pen", "sky", "sky", "blue", "code"}

k = 2

출력 : 

하늘

암호

입력 :

목록 = { "예", "아니요", "예", "예"}

k = 1

출력 : 

상위 K 단어에 대한 설명

주어진 목록 = { "cpp", "java", "java", "cpp", "python", "java", "cpp", "kotlin", "kotlin", "java"} 및 k = 3

각 단어의 총 발생 횟수 –

  • cpp는 주어진 목록에서 3 번 발생했습니다.
  • java는 주어진 목록에서 4 번 발생했습니다.
  • 파이썬은 주어진 목록에서 1 번 발생했습니다.
  • kotlin은 주어진 목록에서 2 번 발생했습니다.

각 단어의 발생 횟수 감소 –

자바, cpp, kotlin, python

따라서 주어진 목록에서 자주 사용되는 상위 k 개 (즉 3 개) 단어는 다음과 같습니다.

  1. 자바
  2. CPP
  3. 코 틀린

상위 K 개 빈번한 단어에 대한 알고리즘

  1. 단어 목록과 정수 k를 초기화합니다.
  2. 지도 및 우선 순위 초기화 변발.
  3. 목록을 탐색하고 맵을 증가시킵니다 [list [i]]].
  4. 맵을 탐색하고 우선 순위 대기열의 크기가 k 미만인지 확인하여 대기열의 현재 요소를 푸시합니다.
  5. 그렇지 않으면 큐의 최상위 요소가 현재 요소보다 작 으면 최상위 요소를 제거하고 현재 요소를 큐에 삽입합니다.
  6. 그렇지 않으면 대기열의 최상위 요소가 현재 요소와 같고 최상위 요소의 키가 현재 요소의 키보다 크면 최상위 요소를 제거하고 현재 요소를 대기열에 삽입합니다.
  7. 빈 목록을 만듭니다.
  8. 큐를 탐색하고 임시 변수에 최상위 요소를 저장하고 최상위 요소를 삭제 한 다음 새 목록에 키를 저장합니다.
  9. 새 목록을 되돌리고 반환하십시오.

상위 k 개의 자주 사용되는 단어를 찾는 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

void frequent(vector<auto> v){
   for(int i = 0; i<v.size(); i++){
      cout<<v[i]<< 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> topFrequent(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;
        }
};

int main(){
    
   Solution s;
   
   vector<string> v = {"code", "sky", "pen", "sky", "sky", "blue", "code"};
   int k = 2;
   frequent(s.topFrequent(v, k));
   
   return 0;
   
}
sky
code

자주 사용되는 상위 k 단어를 찾는 Java 프로그램

import java.util.*;

class text{
    public List<String> topKFrequentAlternate(final String[] words, int k) {
    	final Map<String, Integer> freq = new HashMap<>();
    	
    	final Queue<WordFreq> queue = new PriorityQueue<>((w1, w2) -> {
    		if (w1.getFreq() != w2.getFreq()) {
    			return w1.getFreq() - w2.getFreq();
    		}
    		return w2.getWord().compareTo(w1.getWord());
    	});
    	
    	final List<String> result = new ArrayList<>();
    
    	for (final String word : words) {
    		if (freq.containsKey(word)) {
    			final int count = freq.get(word);
    			freq.put(word, count + 1);
    		} else {
    			freq.put(word, 1);
    		}
    	}
    
    	for (final Map.Entry<String, Integer> entry : freq.entrySet()) {
    		queue.offer(new WordFreq(entry.getKey(), entry.getValue()));
    
    		if (queue.size() > k) {
    			queue.poll();
    		}
    	}
    
    	while (k-- > 0) {
    		result.add(queue.poll().getWord());
    	}
    
    	Collections.reverse(result);
    	return result;
    }
}
class WordFreq {
  private final String word;
  private final int freq;

  WordFreq(final String word, final int freq) {
    this.word = word;
    this.freq = freq;
  }

  String getWord() {
    return this.word;
  }

  int getFreq() {
    return this.freq;
  }

  @Override
  public String toString() {
    return Objects.toString(word) + "->" + Objects.toString(freq);
  }
  
  public static void main (String[] args){
      text t = new text();
      String[] words = {"code", "sky", "pen", "sky", "sky", "blue", "code"};
      int k = 2;
      List<String> res = new ArrayList<String>();
      res = t.topKFrequentAlternate(words,k);
        ListIterator<String> lItr = res.listIterator();
    while (lItr.hasNext()){
      System.out.println(lItr.next());
    }
  }
}
sky
code

참조