Java：Top K问题的解法

Java：Top K问题的解法

import java.util.Arrays;import java.util.PriorityQueue;import java.util.Queue;public class LeafNode { // 堆方法(优先队列) // 1.堆的性质是每次可以找出最大或最小的元素 // 快排变形 public static void main(String[] args) { int[] arr = new int[] { 1, 2, 34, 4, 5, 6 }; //int[] nums = getLeastNumbers(arr, 3); int[] nums=getLeastNumbersTwo(arr,3); System.out.println(Arrays.toString(nums)); } public static int[] getLeastNumbers(int[] arr, int k) { if (k == 0) return new int[0]; // 使用一个最大堆（大顶堆） Queue heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1)); for (int e : arr) { // 当前数字小于堆顶元素才会入堆 if (heap.isEmpty() || heap.size() < k || e < heap.peek()) heap.offer(e); // 删除堆顶最大元素 if (heap.size() > k) heap.poll(); } // 将堆中的元素存入数组 int[] res = new int[heap.size()]; int j = 0; for (int e : heap) res[j++] = e; Arrays.sort(res); return res; } public static int[] getLeastNumbersTwo(int[] arr, int k) { if (k == 0) return new int[0]; else if (arr.length <= k) return arr; // 原地不断划分数组 partitionArray(arr, 0, arr.length - 1, k); // 数组的前 k 个数此时就是最小的 k 个数，将其存入结果 int[] res = new int[k]; for (int i = 0; i < k; i++) res[i] = arr[i]; return res; } static void partitionArray(int[] arr, int lo, int hi, int k) { // 做一次 partition 操作 int m = partition(arr, lo, hi); // 此时数组前 m 个数，就是最小的 m 个数 if(k==m) return;// 正好找到最小的 k(m) 个数 else if(k v) { if (j == lo) break; } if (i >= j) break; swap(a, i, j); } swap(a, lo, j); return j; } static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }}

看起来分治法的快速选择算法的时间、空间复杂度都优于使用堆的方法，但是要注意到快速选择算法的几点局限性：

第一，算法需要修改原数组，如果原数组不能修改的话，还需要拷贝一份数组，空间复杂度就上去了。

第二，算法需要保存所有的数据。如果把数据看成输入流的话，使用堆的方法是来一个处理一个，不需要保存数据，只需要保存 k 个元素的最大堆。而快速选择的方法需要先保存下来所有的数据，再运行算法。当数据量非常大的时候，甚至内存都放不下的时候，就麻烦了。所以当数据量大的时候还是用基于堆的方法比较好。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。