JavaScript版《剑指offer》刷题（28）最小的K个数

- 日理万妓 2021-10-24 03:52 259阅读 0赞

**1.题目描述**

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

**2.题目分析**

这题有三种方法来做。

思路一：先排序，然后在找出最小的。但是有可能数组很大，会超时

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

思路三：利用长度为K的数组，保存k个目前最小的数，然后每次找到里面的最大值和当前值作比较

**3.代码**

思路一代码：

function GetLeastNumbers_Solution(input, k)
    {
        if(input.length < k) return false;
        input.sort(function(a,b){return a-b;});
        return input.slice(0,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;
    }

思路三代码：

参考文章：  
https://www.cnblogs.com/echovic/p/6558985.html  
https://www.cnblogs.com/wuguanglin/p/GetLeastNumbers\_Solution.html  
https://github.com/DavidChen93/-offer-JS-/blob/master/40.1%20%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0.js

基于快速排序思想partiotion查找第K大的数或者第K小的数：  
https://www.cnblogs.com/wuguanglin/p/searchKMax.html