前K个常用字


难度级别 中等
经常问 ol石 风筝 印孚瑟斯
哈希 特里

在前K个常见词问题中,我们给出了一个词列表和一个整数k。 在列表中打印k个最常用的字符串。

前K个常用字

使用案列

输入:

list = {“代码”,“天空”,“笔”,“天空”,“天空”,“蓝色”,“代码”}

k = 2

输出: 

天空

输入:

list = {“是”,“否”,“是”,“是”}

k = 1

输出: 

前K个常用字的解释

令给定列表= {“ cpp”,“ java”,“ java”,“ cpp”,“ python”,“ java”,“ cpp”,“ kotlin”,“ kotlin”,“ java”}},k = 3

每个单词出现的总数–

  • cpp在给定列表中出现3次。
  • 在给定列表中,java出现了4次。
  • python在给定列表中出现1次。
  • 在给定的列表中,kotlin出现了2次。

每个单词出现次数的降序–

Java,CPP,Kotlin,Python

因此,在给定列表中,前k个(即3个)常用词是–

  1. java的
  2. CPP
  3. 科特林

前K个常用词的算法

  1. 初始化单词列表和整数k。
  2. 初始化地图和优先级 队列.
  3. 遍历列表并递增映射[list [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程序查找前k个常用词

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

參考資料