方法一

思路

题目要求找出出现次数前k的字符串，最为简单的就是直接遍历数组统计每个字符串出现的次数，接着再降序排序输出前k的字符串。

具体步骤

• 首先判断k值是否为0，若为0，则直接返回一个空的String二维数组；

• k值大于0时，通过哈希计算每个字符串出现的次数；

• 借助JDK的比较器Collection.sort，自定义降序排序规则，对统计结果进行降序排序；

• 输出排序后的前k个字符串，以及其出现次数。

• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * return topK string
  * @param strings string字符串一维数组 strings
  * @param k int整型 the k
  * @return string字符串二维数组
  */
  public String[][] topKstrings (String[] strings, int k) {
     // write code here
     if (k == 0){
         return new String[][]{};
     }
     String[][] res = new String[k][2];
     TreeMap<String,Integer> map = new TreeMap<>();
     // 统计各个字符串出现的次数
     for (int i=0;i<strings.length;++i){
         String s = strings[i];
         if (!map.containsKey(s)) {
             map.put(s, 1);
         } else {
             map.put(s, map.get(s) + 1);
         }
     }
  
     ArrayList<Map.Entry<String, Integer>> list = 
         new ArrayList<>(map.entrySet());
     // 先是按出现次数降序比较，相同则再按照字符ASCII码降序比较
     Collections.sort(list,
                      (o1, o2) -> 
                      (o1.getValue().compareTo(o2.getValue()) ==
                       0 ? o1.getKey().compareTo(o2.getKey()) : 
                       o2.getValue().compareTo(o1.getValue()))
                     );
     // 返回topK
     for (int i = 0; i < k; i++) {
         res[i][0] = list.get(i).getKey();
         res[i][1] = String.valueOf(list.get(i).getValue());
     }
     return res;
  }
  }

• 时间复杂度：，遍历统计为，但是降序排序需要

• 空间复杂度：，使用hashmap辅助结构。

  方法二

  思路

  方法一的时间复杂度为，而题目中要求时间复杂度为，虽然能够通过测试用例，但是其并不满足要求，而nlogk使我想到了堆这一数据结构，当将堆的大小维持在k时，对于n个数据进行排序，其时间复杂度不是正好为吗，所以本题可以考虑使用最小堆来实现（不使用最大堆是因为为了保证最后堆中存储的元素为topK）。

  具体步骤

• 首先判断k是否为0，k为0，直接返回空字符数组；

• 使用哈希统计每个字符串出现的次数；

• 建立容量为k的最小堆，遍历map，将统计后的字符放入最小堆中，同时需要控制堆中的元素数量，具体过程可以看下图的例子：
  

• 基于最小堆排完序后，再将topK输出到字符数组中，返回即可。

  import java.util.*;
  public class Solution {
  /**
  自定义能够实现升序的比较器
  */
  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();
         }
     }
  }
  /**
  * return topK string
  * @param strings string字符串一维数组 strings
  * @param k int整型 the k
  * @return string字符串二维数组
  */
  public String[][] topKstrings (String[] strings, int k) {
     // write code here
     if (k == 0){
         return new String[][]{};
     }
     Comparator compa = new DescComparator();
     String[][] res = new String[k][2];
     TreeMap<String,Integer> map = new TreeMap<>();
     // 统计各个字符串出现的次数
     for (int i=0;i<strings.length;++i){
         String s = strings[i];
         if (!map.containsKey(s)) {
             map.put(s, 1);
         } else {
             map.put(s, map.get(s) + 1);
         }
     }
     PriorityQueue queue = new PriorityQueue(k,compa);
     for(Map.Entry<String,Integer> entry:map.entrySet()){
         // 堆的元素个数小于k，则直接加入堆中
         if (queue.size() < k) {
             queue.offer(entry);
         } else if (compa.compare(queue.peek(),entry) < 0) {
             //如果堆顶元素 < 新数，则删除堆顶，加入新数入堆
             queue.poll();
             queue.offer(entry);
         }
     }
  
     // 返回topK
     for (int i = k-1; i >=0; --i) {
         Map.Entry<String,Integer> entry =(Map.Entry)queue.poll();
         res[i][0] = entry.getKey();
         res[i][1] = String.valueOf(entry.getValue());
     }
     return res;
  }
  }

• 时间复杂度：，统计为，排序为；

• 空间复杂度：，统计需要。