题目

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

思路

思路1:

先排序,再取前k个数,最小时间复杂度nlogn

思路2:

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

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

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

时间复杂度nlogk,优于思路1。

代码

    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;
        }
      }
    }
Last Updated: 8/2/2019, 10:05:56 PM