【牛客网名企高频面试题】NC97出现次数的TopK问题

NC97 出现次数的TopK问题

题目描述
给定String类型的数组strArr&＃xff0c;再给定整数k&＃xff0c;请严格按照排名顺序打印 出次数前k名的字符串。
[要求]
如果strArr长度为N&＃xff0c;时间复杂度请达到O(N \log K)O(NlogK)

输出K行&＃xff0c;每行有一个字符串和一个整数&＃xff08;字符串表示&＃xff09;。
你需要按照出现出现次数由大到小输出&＃xff0c;若出现次数相同时字符串字典序较小的优先输出

示例1
输入

[“1”,“2”,“3”,“4”],2

返回值

[[“1”,“1”],[“2”,“1”]]

示例2
输入

[“1”,“1”,“2”,“3”],2

返回值

[[“1”,“2”],[“2”,“1”]]

代码&＃xff1a;

import java.util.*;public class Solution {/*** return topK string* &＃64;param strings string字符串一维数组 strings* &＃64;param k int整型 the k* &＃64;return string字符串二维数组*/public String[][] topKstrings (String[] strings, int k) {// write code hereHashMap<String,Integer> map &＃61; new HashMap<>();for(String str:strings){if(map.containsKey(str)){map.put(str,map.get(str)&＃43;1);}else{map.put(str,1);}}/**不太明白。。。。。。*/Set<Map.Entry<String,Integer>> set &＃61; map.entrySet();List<Map.Entry<String,Integer>> list &＃61; new ArrayList<>(set);Collections.sort(list, new Comparator<Map.Entry<String, Integer>>(){&＃64;Overridepublic int compare(Map.Entry<String, Integer> entryOne, Map.Entry<String, Integer> entryTwo) {if (entryOne.getValue() !&＃61; entryTwo.getValue())return entryTwo.getValue() - entryOne.getValue();return entryOne.getKey().compareTo(entryTwo.getKey());}});String[][] res &＃61; new String[k][2];for(int i&＃61;0;i<k;i&＃43;&＃43;){res[i][0] &＃61; list.get(i).getKey();res[i][1] &＃61; list.get(i).getValue().toString();}return res;}
}