数组中的第 K 个最大元素

熟悉一下快排和堆排

• 数组中的第 K 个最大元素
  • 题目详情
  • 堆排序
  • 快速排序

题目详情

给定整数数组nums和整数k，请返回数组中第k个最大的元素。

请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

你必须设计并实现时间复杂度为O(n) 的算法解决此问题。

堆排序

建立一个大顶堆，做 k−1 次删除操作后,堆顶元素就是我们要找的答案

  let n = nums.length;
  buildMaxHeap(nums, n);

  for (let i = n - 1; i >= n - k + 1; i--) {
    swap(nums, 0, i);
    n--;
    heapify(nums, n, 0);
  }

  return nums[0];

function buildMaxHeap(arr, n) {
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    //比较节点 i 和它的左右子节点，如果 i 不是最大的，就将它与最大的子节点交换
    heapify(arr, n, i);
  }
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function heapify(arr, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== i) {
    swap(arr, i, largest);
    heapify(arr, n, largest);
  }

快速排序

使用快排会导致内存占用过大

  if (nums.length === 1) return nums[0];
  const pivot = nums[nums.length - 1];
  const left = [];
  const right = [];
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > pivot) {
      right.push(nums[i]);
    } else {
      left.push(nums[i]);
    }
  }
  if (k <= right.length) {
    return findKthLargest(right, k);
  } else if (k > nums.length - left.length) {
    return findKthLargest(left, k - right.length - 1);
  }
  return pivot;