两次堆排序+关联数组 我这个程序采用的是泛型，本来不是为了这道题而写，而是为了这一类题，使得不管输入的任何类型都可以计算前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; } @Override public int compareTo(Node o) { return -(this.value.compareTo(o.value)); } @Override public String toString(){ return key.toString()+ " "; } public K getKey(){ return key; } }