کلمات متداول برتر K


سطح دشواری متوسط
اغلب در همبستگی فورکایت Infosys در
هشی کردن پشته مرتب سازی

در مسئله کلمات متداول K ، لیستی از کلمات و یک عدد صحیح k آورده ایم. k رشته های پرکاربرد را در لیست چاپ کنید.

کلمات متداول برتر K

مثال

ورودی:

list = {"کد" ، "آسمان" ، "قلم" ، "آسمان" ، "آسمان" ، "آبی" ، "کد"}

k = 2

خروجی: 

آسمان

رمز

ورودی:

list = {"بله" ، "نه" ، "بله" ، "بله"}

k = 1

خروجی: 

بله

توضیح کلمات متداول Top K

اجازه دهید لیست داده شده = {"cpp" ، "java" ، "java" ، "cpp" ، "python" ، "java" ، "cpp" ، "kotlin" ، "kotlin" ، "java"} و k = 3

تعداد کل وقوع هر کلمه -

  • cpp 3 بار در لیست داده شده رخ داده است.
  • جاوا 4 بار در لیست داده شده رخ داده است.
  • پایتون 1 بار در لیست داده شده رخ داده است.
  • kotlin 2 بار در لیست داده شده رخ داده است.

کاهش ترتیب وقوع هر کلمه -

جاوا ، cpp ، kotlin ، پایتون

بنابراین ، کلمات بالایی k (یعنی 3) که اغلب در لیست داده شده استفاده می شوند عبارتند از -

  1. جاوه
  2. cpp
  3. کوتلین

الگوریتمی برای کلمات کلیدی Top K

  1. لیستی از کلمات و یک عدد ص را مقداردهی اولیه کنید.
  2. یک نقشه و یک اولویت را آغاز کنید صف.
  3. لیست و نقشه افزایشی را رد کنید [فهرست [من]]].
  4. نقشه را رد کنید و بررسی کنید که آیا اندازه صف اولویت کمتر از k فشار عنصر فعلی در صف است.
  5. اگر عنصر بالایی در صف کمتر از عنصر فعلی باشد ، عنصر بالایی را حذف کرده و عنصر فعلی را در صف قرار می دهد ، از بین برود.
  6. اگر عنصر بالایی در صف برابر با عنصر فعلی باشد کلید دیگری از عنصر فعلی بیشتر از کلید عنصر فعلی است که عنصر بالایی را برداشته و عنصر فعلی را در صف قرار دهید
  7. یک لیست خالی ایجاد کنید.
  8. صف را رد کنید و عنصر برتر را در آن در یک متغیر موقت ذخیره کنید ، عنصر بالا را حذف کرده و کلید آن را در لیست جدید ذخیره کنید.
  9. لیست جدید را معکوس کنید و آن را برگردانید.

برنامه C ++ برای یافتن کلمات متداول k

#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

برنامه جاوا برای یافتن کلمات متداول برتر

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

منابع