《剑指offer》— JavaScript（29）最小的K个数

最小的K个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

思路一

使用JavaScript的Array对象的sort()方法进行自小到大排序，然后输出最小的k个数。

实现代码

function GetLeastNumbers_Solution(input, k)
{
    if(input.length < k) return false;
    input.sort(function(a,b){return a-b;});
    return input.slice(0,k);
}

思路二

1. 利用快速排序的原理解决问题。
   2.基于数组的第k个数字来调整，使得比第k个数字晓得所有数字都位于其左边，比第k个数字大的所有数字都位于数组的右边。
2. 调整之后，位于数组左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。

实现代码

//交换数组元素的值
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]; //设置哨兵
    var i = start; //交换的次数+1 哨兵要在数组插入的位置
    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;
}