Interview question 17.14. Minimum K number
Sort slice returns a new array
var smallestK = function(arr, k) {
arr.sort((a, b) = > a - b);
return arr.slice(0, k);
};
Copy the code
Fast row
/ * * *@param {number[]} arr
* @param {number} k
* @return {number[]}* /
var smallestK = function(arr, k) {
randomizedSelected(arr, 0, arr.length - 1, k);
return arr.slice(0, k);
}
const randomizedSelected = (arr, l, r, k) = > {
if (l >= r) {
return;
}
const pos = randomizedPartition(arr, l, r);
const num = pos - l + 1;
if (k === num) {
return;
} else if (k < num) {
randomizedSelected(arr, l, pos - 1, k);
} else {
randomizedSelected(arr, pos + 1, r, k - num); }}const randomizedPartition = (nums, l, r) = > {
const i = parseInt(Math.random() * (r - l + 1)) + l;
swap(nums, r, i);
return partition(nums, l, r);
}
const partition = (nums, l, r) = > {
const pivot = nums[r];
let i = l - 1;
for (let j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
// let i = l, j = r;
// while (true) {
// while(nums[i++] < pivot) {}
// while(nums[--j] > pivot) {}
// if (i < j) {
// swap(nums, i, j)
/ /}
// else break
// }
// swap(nums, i + 1, r)
// return i + 1
}
const swap = (nums, i, j) = > {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
Copy the code