《剑指offer》最小的k个数

本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法，也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。

题目

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

思路

1.把前k个数构建一个大顶堆

2.从第k个数开始，和大顶堆的最大值进行比较，若比最大值小，交换两个数的位置，重新构建大顶堆

3.一次遍历之后大顶堆里的数就是整个数据里最小的k个数。

代码

代码语言：javascript复制

    function GetLeastNumbers_Solution(input, k) {      if (k > input.length) {        return [];      }      createHeap(input, k);      for (let i = k; i < input.length; i  ) {        // 当前值比最小的k个值中的最大值小        if (input[i] < input[0]) {          [input[i], input[0]] = [input[0], input[i]];          ajustHeap(input, 0, k);        }      }      return input.splice(0, k);    }
    // 构建大顶堆    function createHeap(arr, length) {      for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {        ajustHeap(arr, i, length);      }    }
    function ajustHeap(arr, index, length) {      for (let i = 2 * index   1; i < length; i = 2 * i   1) {        if (i   1 < length && arr[i   1] > arr[i]) {          i  ;        }        if (arr[index] < arr[i]) {          [arr[index], arr[i]] = [arr[i], arr[index]];          index = i;        } else {          break;        }      }    }

javascript leetcode

0 人点赞