最小的K個數(shù)
題目描述
輸入n個整數(shù)，找出其中最小的K個數(shù)蝇闭。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字芯侥，則最小的4個數(shù)字是1,2,3,4焰轻。
思路一
使用JavaScript的Array對象的sort()方法進行自小到大排序，然后輸出最小的k個數(shù)聪舒。
實現(xiàn)代碼
function GetLeastNumbers_Solution(input, k)
{
if(input.length < k) return false;
input.sort(function(a,b){return a-b;});
return input.slice(0,k);
}
思路二
- 利用快速排序的原理解決問題辨液。
2.基于數(shù)組的第k個數(shù)字來調(diào)整，使得比第k個數(shù)字曉得所有數(shù)字都位于其左邊箱残，比第k個數(shù)字大的所有數(shù)字都位于數(shù)組的右邊滔迈。 - 調(diào)整之后，位于數(shù)組左邊的k個數(shù)字就是最小的k個數(shù)字（這k個數(shù)字不一定是排序的）被辑。
實現(xiàn)代碼
//交換數(shù)組元素的值
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partation(arr, start, end) {
var pivot = arr[end]; //設(shè)置哨兵
var i = start; //交換的次數(shù)+1 哨兵要在數(shù)組插入的位置
for (var j = start; j < end; j++) {
if (arr[j] < pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, end);
return i;
}
function GetLeastNumbers_Solution(input, k) {
var result = [];
if (input.length < 0 || k > input.length || k <= 0) {
return false;
}
var start = 0;
var end = input.length - 1;
var p = partation(input, start, end);
while (p !== (k - 1)) {
if (p > (k - 1)) {
end = p - 1;
p = partation(input, start, end);
} else {
start = p + 1;
partation(input, start, end);
}
}
for (var i = 0; i < k; i++) {
result.push(input[i]);
}
return result;
}
