最小的 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;
}