למעלה K מילים תכופות


רמת קושי בינוני
נשאל לעתים קרובות נאמן פורקיטים אינפוסיס
חבטות ערימה טרי

בבעיית מילים תכופות בראש K, נתנו רשימת מילים ומספר שלם k. הדפס את k המחרוזות הנפוצות ביותר ברשימה.

למעלה K מילים תכופות

דוגמה

קלט:

רשימה = {"קוד", "שמיים", "עט", "שמיים", "שמיים", "כחול", "קוד"}

k = 2

פלט: 

שמים

קוד

קלט:

list = {“כן”, “לא”, “כן”, “כן”}

k = 1

פלט: 

כן

הסבר למילים K תכופות מובילות

תן לרשימה הנתונה = {"cpp", "java", "java", "cpp", "python", "java", "cpp", "kotlin", "kotlin", "java"} ו- k = 3

המספר הכולל של המופע של כל מילה -

  • cpp התרחש 3 פעמים ברשימה הנתונה.
  • java התרחש 4 פעמים ברשימה הנתונה.
  • פיתון התרחש פעם אחת ברשימה הנתונה.
  • kotlin התרחש פעמיים ברשימה הנתונה.

סדר יורד של מספר המופעים של כל מילה -

ג'אווה, cpp, kotlin, python

לכן, המילים העליונות (כלומר 3) הנפוצות ברשימה הנתונה הן -

  1. תאווה
  2. cpp
  3. קוטלין

אלגוריתם למילים תכופות ב- K

  1. אתחל רשימת מילים ומספר שלם k.
  2. אתחל מפה וסדר עדיפות תור.
  3. חצו את הרשימה ומפת התוספת [רשימה [i]]].
  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

תוכנית 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

הפניות