两次堆排序+关联数组
我这个程序采用的是泛型，本来不是为了这道题而写，而是为了这一类题，使得不管输入的任何类型都可以计算前K个高频元素
因为要遵循题目格式，所以代码比较乱，之后会写成工具类放在github上，
欢迎大家star

class Solution {private static int size;private static <T extends Comparable> void build(List<T> t) {int pos = 1;size = t.size();while ((2 * pos) <= t.size() || (2 * pos + 1) <= t.size()) {pos++;}pos--;while (pos != 0) {sink(t, pos);pos--;}}private static <T extends Comparable> void sink(List<T> t, int pos) {if (2 * pos > size) {return;}T left = t.get(2 * pos - 1);T min = left;int changeIndex = 2 * pos;T temp = t.get(pos - 1);if (2 * pos + 1 <= size) {T right = t.get(2 * pos);if (left.compareTo(right) > 0) {min = right;changeIndex++;}}if (temp.compareTo(min) > 0) {t.set(changeIndex - 1, temp);t.set(pos - 1, min);sink(t, changeIndex);}}public static <T extends Comparable> List<T> heapSort(List<T> t) {if (t.size() == 1) {return t;}build(t);return heapSortCore(t);}private static <T extends Comparable> List<T> heapSortCore(List<T> t) {int size_temp = size;List<T> temp = null;if (t instanceof ArrayList) {temp = new ArrayList<T>(size_temp);}if (t instanceof LinkedList) {temp = new LinkedList<T>();}while (size_temp > 0) {temp.add(pop(t));size_temp--;}return temp;}private static <T extends Comparable> T pop(List<T> t) {T first = t.get(0);t.set(0, t.get(size - 1));T temp = t.remove(size - 1);size--;sink(t, 1);return first;}public int[] topKFrequent(int[] nums, int k) {Integer[] numInteger = new Integer[nums.length];for (int i = 0; i < nums.length; i++) {numInteger[i] = new Integer(nums[i]);}List<Integer> lists = new ArrayList<>(Arrays.asList(numInteger));lists = Solution.heapSort(lists);List<Node> result = new ArrayList<Node>();Integer[] count = new Integer[lists.size()];count[0] = 1;for (int i = 1; i < lists.size(); i++) {if (lists.get(i).equals(lists.get(i - 1))) {count[i] = count[i - 1] + 1;} else {count[i] = 1;}}List<Node> listNode = new ArrayList<>();for (int i = count.length - 1; i >= 0; ) {listNode.add(new Node().setKeyAndValue(lists.get(i), count[i]));i = i - count[i];}result = Solution.heapSort(listNode);Integer[] result_Node = (Integer[]) result.stream().limit(k).map(t -> t.getKey()).toArray(Integer[]::new);int[] resultReal = new int[result_Node.length];for (int i = 0; i < resultReal.length; i++) {resultReal[i] = result_Node[i].intValue();}return resultReal;}
}
class Node <K,V extends Comparable> implements Comparable<Node>{private K key;private V value;public Node<K, V> setKeyAndValue(K key,V value){this.key = key;this.value = value;return this;}@Overridepublic int compareTo(Node o) {return -(this.value.compareTo(o.value));}@Overridepublic String toString(){return key.toString()+ " ";}public K getKey(){return key;}
}