347. Top K Frequent Elements 发表于 2022-01-17 Priority Queue12345678910111213141516171819202122232425262728293031class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> valueToCountMap = new HashMap<>(); for (int num : nums) { valueToCountMap.put(num, valueToCountMap.getOrDefault(num, 0) + 1); } int[][] valueToCountArray = new int[valueToCountMap.size()][]; int i = 0; for (Map.Entry<Integer, Integer> entry : valueToCountMap.entrySet()) { valueToCountArray[i++] = new int[]{entry.getKey(), entry.getValue()}; } Queue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1])); for (int j = 0; j < k; j++) { minHeap.offer(valueToCountArray[j]); } for (int j = k; j < valueToCountArray.length; j++) { if (valueToCountArray[j][1] > minHeap.peek()[1]) { minHeap.poll(); minHeap.offer(valueToCountArray[j]); } } int[] res = new int[k]; for (int j = 0; j < k; j++) { res[j] = minHeap.poll()[0]; } return res; }} QuickSort12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576class Solution { private static class Element { private final int freq; private final int val; public Element(int freq, int val) { this.freq = freq; this.val = val; } } public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> valueToFreqMap = new HashMap<>(); for (int num : nums) { valueToFreqMap.put(num, valueToFreqMap.getOrDefault(num, 0) + 1); } Element[] elements = new Element[valueToFreqMap.size()]; int index = 0; for (Map.Entry<Integer, Integer> entry : valueToFreqMap.entrySet()) { elements[index++] = new Element(entry.getValue(), entry.getKey()); } quickSort(elements, 0, elements.length - 1, k - 1); int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = elements[i].val; } return res; } private void quickSort(Element[] elements, int left, int right, int targetIndex) { if (left >= right) { return; } while (true) { int pivotIndex = partition(elements, left, right); if (pivotIndex < targetIndex) { left = pivotIndex + 1; } else if (pivotIndex > targetIndex) { right = pivotIndex - 1; } else { return; } } } private int partition(Element[] elements, int left, int right) { int randomIndex = left + ThreadLocalRandom.current().nextInt(right - left + 1); Element pivotElement = elements[randomIndex]; swap(elements, left, randomIndex); // 注意此处是交换至 left 索引而不是 0 int i = left, j = right; while (i < j) { while (i < j && elements[j].freq <= pivotElement.freq) { j--; } while (i < j && elements[i].freq >= pivotElement.freq) { i++; } swap(elements, i, j); } swap(elements, left, i); // 注意此处是交换至 left 索引而不是 0 return i; } private void swap(Element[] elements, int i, int j) { Element tmp = elements[i]; elements[i] = elements[j]; elements[j] = tmp; }} Reference347. Top K Frequent Elements剑指 Offer II 060. 出现频率最高的 k 个数字