NC97 字符串出现次数的TopK问题
描述
给定一个字符串数组,再给定整数k,请返回出现次数前k名的字符串和对应的次数。
返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率,按字典序排序。
对于两个字符串,大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
比如"ah1x"小于"ahb",“231”<”32“
字符仅包含数字和字母
[要求]
如果字符串数组长度为N,时间复杂度请达到O(N \log K)O(NlogK)
import java.util.*;
public class Solution {
/**
* return topK string
* @param strings string字符串一维数组 strings
* @param k int整型 the k
* @return string字符串二维数组
*/
class DescComparator implements Comparator<Map.Entry<String,Integer>>
{
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
if (o1.getValue().equals(o2.getValue())){
//字典序小的在前 所以 o1 比 o2
return o2.getKey().compareTo(o1.getKey());
}else {
//数量小的在前所以 o1 - o2
return o1.getValue() - o2.getValue();
}
}
}
public String[][] topKstrings (String[] strings, int k) {
// write code here
String[][] res = new String[k][2] ;
if(strings == null || strings.length == 0){
return null ;
}
if(k == 0){
return new String[][]{};
}
TreeMap<String , Integer> map = new TreeMap<>() ;
for(int i = 0 ; i < strings.length ; i++){
if(map.containsKey(strings[i])){
map.put(strings[i] , map.get(strings[i])+1) ;
}else{
map.put(strings[i] , 1) ;
}
}
Comparator compa = new DescComparator();
PriorityQueue minHead = new PriorityQueue(k , compa);
for(Map.Entry<String, Integer> entry : map.entrySet()){
if(minHead.size() < k){
minHead.offer(entry) ;
//continue ;
}
else if(compa.compare(minHead.peek() , entry) < 0){
minHead.poll();
minHead.offer(entry) ;
}
}
for(int i = k-1 ; i >= 0 ; i--){
Map.Entry<String , Integer> node = (Map.Entry)minHead.poll();
res[i][0] = node.getKey();
res[i][1] = String.valueOf(node.getValue()) ;
}
return res ;
}
}