问题描述

给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印 出次数前k名的字符串。
如果strArr长度为N，时间复杂度请达到O(NlogK)
输出K行，每行有一个字符串和一个整数（字符串表示）。
你需要按照出现出现次数由大到小输出，若出现次数相同时字符串字典序较小的优先输出

示例

示例1

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

输出
[[“1”,“1”],[“2”,“1”]]

解决思路

思路

1. 对数组进行遍历统计，然后进行排序，排序后输出前k个即可
2. 说到TOPK我们可能优先想到的是使用堆，但操作比较复杂，本文件不做介绍

代码实现

// 思路1
public class Solution {  
   public String[][] topKstrings (String[] strings, int k) {
        // write code here
        Map<String, Integer> map = new HashMap<>();
        for (String string : strings) {
            if (map.containsKey(string)) {
                map.put(string, map.get(string) + 1);
            } else {
                map.put(string, 1);
            }
        }

        List<Counter> counterList = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            counterList.add(new Counter(entry.getKey(), entry.getValue()));
        }

        Collections.sort(counterList, (o1, o2) -> {
            if (o1.count == o2.count) {
                return o1.str.compareTo(o2.str);
            } else {
                return o2.count - o1.count;
            }
        });
        String[][] result = new String[k][2];
        for (int i = 0; i < k; i++) {
            result[i][0] = counterList.get(i).str;
            result[i][1] = counterList.get(i).count.toString();
        }

        return result;
    }

    class Counter {
        String str;
        Integer count;

        public Counter(String str, Integer count) {
            this.str = str;
            this.count = count;
        }

        @Override
        public String toString() {
            return "Counter{" +
                    "str='" + str + '\'' +
                    ", count=" + count +
                    '}';
        }
    }
}

时间复杂度分析：
O(N)：遍历数组

空间复杂度分析：
O(N)：数组没有重复的，map存储了N个元素

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

出现次数的TopK问题-牛客网