54 lines
1.2 KiB
JavaScript
54 lines
1.2 KiB
JavaScript
/**
|
|
*
|
|
* @param {number[]} arr - 需要操作的数组
|
|
* @param {number} k - 需要找的多少个数
|
|
*/
|
|
function topK(arr, k) {
|
|
if (k > arr.length) {
|
|
throw new Error(`数组的长度必须大于${k}`);
|
|
}
|
|
let low = 0;
|
|
let high = arr.length - 1;
|
|
let pivot = partition(arr, low, high);
|
|
while (pivot !== k - 1) { // 如果k等于pivot-1说明就找到了
|
|
if (pivot > k - 1) {
|
|
high = pivot - 1;
|
|
pivot = partition(arr, low, high);
|
|
}
|
|
if (pivot < k - 1) {
|
|
low = pivot + 1;
|
|
pivot = partition(arr, low, high);
|
|
}
|
|
}
|
|
return arr.slice(0, k);
|
|
}
|
|
|
|
/**
|
|
* @description 使用经典的挖坑法
|
|
* @param {number[]} 要分解的数组
|
|
* @param {*} low 开始下标
|
|
* @param {*} high 结束下标
|
|
*/
|
|
function partition(arr, low, high) {
|
|
const pivot = arr[high]; // 默认以最后一个数为枢纽
|
|
while (low < high) {
|
|
// low找比pivot大的数
|
|
while (low < high && arr[low] < pivot) {
|
|
low++;
|
|
}
|
|
arr[high] = arr[low];
|
|
while (low < high && arr[high] > pivot) {
|
|
high--;
|
|
}
|
|
arr[low] = arr[high];
|
|
}
|
|
arr[low] = pivot;
|
|
return low;
|
|
}
|
|
|
|
// test
|
|
|
|
const arr = [11, 9, 6, 17, 0, 1, 2, 18, 3, 4, 8, 5];
|
|
const ret = topK(arr, 100);
|
|
console.log(ret);
|