百分点：算法：前K个最大的元素（一面）

[foreverzmy]

To：
foreverzmy

面试公司：
百分点

面试环节：
一面

问题：
算法：前K个最大的元素

[foreverzmy]

解法一：
最简单的方法就是对数组进行排序，然后取前 K 位就可以了。

/**
 * 查找前 K 个最大的元素
 * 
 * @param {number[]} arr - 要查询的数组
 * @param {number} k - 最大个数
 * 
 * @return {number[]}
 */
const findKMax = (arr, k) => {
  return arr.sort((a, b) => b - a).slice(0, k);
}

[foreverzmy]

解法二：

解法一用了 js 的 sort 来实现排序，但是复杂度比较高，数据量大的话会比较慢，下面看一个用类似快速排序的分治法的实现：

假设有 n 个数存在数组 S 中，从数组 S 中随机找一个元素 X，遍历数组，比 X 大的放在 S1 中，比 X 小的放在 S2 中，那么会出现以下三种情况：

1. S1 的数字个数等于 K，结束查找，返回 S1;
2. S1 的数字个数大于 K，继续在 S1 中找取最大的K个数字;
3. S1 的数字个数小于 K，继续在 S2 中找取最大的 K-S1.length 个数字，拼接在 S1 后;
   这样递归下去，就可以找出答案来了。下面看具体的实现：

/**
 * 分割数组
 * 
 * @typedef {Object} Partition
 * @property {number[]} Partition.maxarr
 * @property {number[]} Partition.minarr
 * 
 * @param {number[]} arr - 要分割的数组
 * 
 * @returns {Partition} res - 返回结果
 */
const partition = (arr) => {
  const length = arr.length; // 数组长度

  const mid = ~~(length / 2); // 取数组中间的位置，可随机
  const middle = arr[mid]; // 数组中间的值
  const maxarr = []; // 比中间值大
  const minarr = []; // 比中间值小

  // 数组长度为 2 的要特殊处理
  if (length === 2) {
    maxarr.push(Math.max(arr[0], arr[1]));
    minarr.push(Math.min(arr[0], arr[1]));
  } else {
    arr.forEach((v, i) => {
      if (i !== mid) {
        if (v >= middle) {
          maxarr.push(v);
        } else {
          minarr.push(v);
        }
      }
    })

    // 将中间值放到 maxarr 的最后一位
    maxarr.push(middle);
  }

  return { maxarr, minarr }
}

/**
 * 查找前 K 个最大的元素
 * 
 * @param {number[]} arr - 要查询的数组
 * @param {number} k - 最大个数
 * 
 * @return {number[]}
 */
const findKMax = (arr, k) => {

  if (arr.length < k) {
    return arr;
  }

  // 分割数组
  const { maxarr, minarr } = partition(arr);

  if (maxarr.length === k) {
    return maxarr;
  }

  if (maxarr.length > k) {
    return findKMax(maxarr, k);
  }

  if (maxarr.length < k) {
    return maxarr.concat(findKMax(minarr, k - maxarr.length));
  }
}

[foreverzmy]

解法三：

可以取数组的前 K 位构建一个小顶堆，这么堆顶就是前 K 位最小的值，然后从 K+1 遍历数组，如果小于堆顶，则将其交换，并重新构建堆，使堆顶最小，这么遍历结束后，堆就是最大的 K 位，堆顶是前 K 位的最小值。

/**
 * 小顶堆叶子节点排序
 * @param {number[]} arr - 堆
 * @param {number} i = 父节点
 * @param {length} i - 堆大小
 */
const heapify = (arr, i, length) => {
  const left = 2 * i + 1; // 左孩子节点
  const right = 2 * i + 2; // 右孩子节点
  let minimum = i; // 假设最小的节点为父结点

  // 确定三个节点的最小节点
  if (left < length && arr[left] < arr[minimum]) {
    minimum = left;
  }

  if (right < length && arr[right] < arr[minimum]) {
    minimum = right;
  }

  // 如果父节点不是最小节点
  if (minimum !== i) {
    // 最小节点和父节点交换
    const tmp = arr[minimum];
    arr[minimum] = arr[i];
    arr[i] = tmp;

    // 对调整的结点做同样的交换
    heapify(arr, minimum, length);
  }

}

/**
 * 构建小顶堆
 * 从 n/2 个节点开始，依次构建堆，直到第一个节点
 * 
 * @param {number[]} arr 
 */
const buildMinHeap = (arr) => {
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    heapify(arr, i, arr.length)
  }
  return arr;
}

/**·
 * 查找前 K 个最大的元素
 * 
 * @param {number[]} arr - 要查询的数组
 * @param {number} k - 最大个数
 * 
 * @return {number[]}
 */
const findKMax = (arr, k) => {
  // 取数组的前 K 位构建小顶堆
  const newArr = [...arr];
  const kMax = arr.slice(0, k)
  buildMinHeap(kMax);

  // 堆后面的进行遍历，如果比堆顶大，则交换并重新构建堆
  for (let i = k; i < newArr.length; i++) {
    if (newArr[i] > kMax[0]) {
      const tmp = kMax[0];
      kMax[0] = newArr[i];
      newArr[i] = tmp;

      buildMinHeap(kMax);
    }
  }

  return kMax;
}