小米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<java.util.List<Integer>> list = new java.util.ArrayList<java.util.List<Integer>>(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;
	}