小米OJ上分日记——（十三）出现频率最高的前 K 个元素

序号：#13
难度：有挑战
时间限制：1000ms
内存限制：10M
描述
有一个不为空且仅包含正整数的数组，找出其中出现频率最高的前 K 个数，时间复杂度必须在 O(n log n) 以内。

输入
一行数据包括两部分，一个正整数数组（数字间 ‘,’ 分隔）和一个正整数 K （1 ≤ K ≤ 数组长度），数组和 K 之间有一个空格。

输出
输出包含前 K 个出现频率最高的数（出现频率相同时，较小的数在前），用 ', ’ 分隔，保证升序排列。

输入样例

1,1,1,2,2,3 2

输出样例

1,2

解析：做了很久，一个一个bug排查，结果运行出来运行时间超越了0%的人，垃圾算法，思路仅供参考。

/**
* 已引入：
* java.util.*
* 要使用其他 jar 包请使用完整路径，如：
* java.util.List> list = new java.util.ArrayList>(100);
* @param  line 为单行测试数据
* @return 处理后的结果
*/
private static String solution(String line) {String[] str = line.split(" ");String[] str1 = str[0].split(",");int[] a = new int[str1.length];for (int i = 0; i < a.length; i++) {a[i] = Integer.parseInt(str1[i]);}int[] times = new int[getMax(a) + 1];int outNum = Integer.parseInt(str[1]);String result = "";for (int i = 0; i < str1.length; i++) {times[Integer.parseInt(str1[i])]++;}int count = 0;String[] MAX = new String[outNum];for (int i = 0; i < times.length; i++) {int t=getMax(times);if (times[i] == t) {MAX[count] = Integer.toString(i);times[i] = 0;count++;if (count != outNum) {i=0;}else{break;}}}result = String.join(",", MAX);return result;}static int getMax(int a[]) {int max = a[0];for (int i = 0; i < a.length; i++) {if (max < a[i]) {max = a[i];}}return max;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！