最小的k个数
题解
最小的k个数
就是求最小的几个数，把数组元素从小到大排列，而后输入后面的k个数就能够了，而后把这几个数赋给新的数组再返回就行
堆
PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素能够默认天然排序或者通过提供的Comparator（比拟器）在队列实例化的时排序。要求应用Java Comparable和Comparator接口给对象排序，并且在排序时会依照优先级解决其中的元素。
(i1, i2) -> Integer.compare(i2, i1))
由从小到大排序变为从大到小排序
堆
疾速排序
public int[] getLeastNumbers(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;}void partitionArray(int[] arr, int lo, int hi, int k) { // 做一次 partition 操作 int m = partition(arr, lo, hi); // 此时数组前 m 个数，就是最小的 m 个数 if (k == m) { // 正好找到最小的 k(m) 个数 return; } else if (k < m) { // 最小的 k 个数肯定在前 m 个数中，递归划分 partitionArray(arr, lo, m-1, k); } else { // 在右侧数组中寻找最小的 k-m 个数 partitionArray(arr, m+1, hi, k); }}// partition 函数和疾速排序中雷同，具体可参考疾速排序相干的材料// 代码参考 Sedgewick 的《算法4》int partition(int[] a, int lo, int hi) { int i = lo; int j = hi + 1; int v = a[lo]; while (true) { while (a[++i] < v) { if (i == hi) { break; } } while (a[--j] > v) { if (j == lo) { break; } } if (i >= j) { break; } swap(a, i, j); } swap(a, lo, j); // a[lo .. j-1] <= a[j] <= a[j+1 .. hi] return j;}void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp;}