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 ;
    }
}