解法一 随机切分

随机抽取数组中一个元素进行切分并返回该元素下标 index：

index == k-1 切分元素正好为第k个元素index < k-1 第k大的元素在下标为index元素的右边，对index右边的元素进行切分index > k-1 第k大的元素在下标为index元素的左边，对index左边的元素进行切分 class Solution { Random rand = new Random(); public int[] getLeastNumbers(int[] arr, int k) { if(arr == null || arr.length == 0 || arr.length < k || k <= 0) return new int[]{}; int lo = 0; int hi = arr.length - 1; int index = partition(arr, lo, hi); while(index != k - 1){ if(index > k - 1){ hi = index - 1; index = partition(arr, lo, hi); }else if(index < k - 1){ lo = index + 1; index = partition(arr, lo, hi); } } return Arrays.copyOfRange(arr, 0, k); } /** * 随机切分函数 */ private int partition(int[] a, int lo, int hi){ if(a == null || a.length == 0 || lo < 0 || hi > a.length) throw new RuntimeException("Invalid Parameters"); int index = randRange(rand, lo, hi+1); System.out.println(index); exch(a, hi, index); int small = lo - 1; for(index = lo; index < hi; ++index){ if(a[index] < a[hi] ){ ++small; if(index != small){ exch(a, small, index); } } } small++; exch(a, small, hi); return small; } private int randRange(Random rand, int min, int max) { if(max - min == 0) return min; int r = rand.nextInt(max - min) + min; return r; } private void exch(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

最大堆优先队列 适用于大量数据

使用一个容器添加k个数字。容器含有k个数字之后将新的数字与容器中的最大数字比较，如果新数大于最大值则新数不可能为最小的k个数之一，如果新数小于最大值则将容器的最大值提出，加入新数。 从容器中快速查询最大数可以使用最大优先队列，查询时间复杂度为O(1)，基于堆实现的的最大优先队列可以在O(logk)实现删除与插入操作。

class Solution { public int[] getLeastNumbers(int[] arr, int k) { if(arr == null || arr.length == 0 || arr.length < k || k <= 0) return new int[]{}; PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer o1, Integer o2) { return o2-o1; } }); for(Integer each : arr){ if(maxPQ.size() < k){ maxPQ.add(each); }else if(each < maxPQ.peek()){ maxPQ.poll(); maxPQ.offer(each); } } int[] ans = new int[k]; for(int i = 0; i < k; i++){ ans[i] = maxPQ.poll(); } return ans; } }

参考

采用PriorityQueue实现大小顶堆 解决topK问题