数组中的第-k-个最大元素

Tips

题目类型: topK

相关题目:

• 剑指 Offer - 40. 最小的 k 个数
• 347. 前-k-个高频元素

题目

在未排序的数组中找到第 k 个最大的元素. 请注意, 你需要找的是数组排序后的第 k 个最大的元素, 而不是第 k 个不同的元素.

示例

输入: [3, 2, 1, 5, 6, 4] 和 k = 2

输出: 5

题解

JavaScript - 大顶堆

Top K 的问题首先可以用优先队列解决.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const maxHeap = new PriorityQueue()

  for (const num of nums) {
    maxHeap.offer(num)
  }

  while (--k > 0) {
    maxHeap.poll()
  }

  return maxHeap.peek()
}

JavaScript - 小顶堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const minHeap = new MinPriorityQueue()

  for (const num of nums) {
    minHeap.offer(num)
  }

  for (let j = 0; j < nums.length - k; j++) {
    minHeap.poll()
  }

  return minHeap.peek()
}

Rust - 大顶堆

use std::collections::BinaryHeap;

pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
    let mut k = k - 1;
    let mut heap = BinaryHeap::new();

    for val in nums {
        heap.push(val);
    }

    while k > 0 {
        heap.pop();
        k -= 1;
    }

    *heap.peek().unwrap()
}

JavaScript - 快速选择算法

我们在快速排序中了解到了 partition 函数, 它是用来找每个子区间的分界点 p, 以保证分界点的左侧都小于 p, 右边的都大于 p. 题目要求的是第 k 个最大元素, 这个元素其实就是 nums 升序排序后索引为 nums.length - k 的元素.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const n = nums.length
  return quickselect(nums, 0, n - 1, n - k) // 调用 quickselect 寻找第 n-k 小的元素
}

/**
 * 快速选择算法, 找到第 k 大的元素
 * @param {number[]} nums - 输入的数组
 * @param {number} l - 当前搜索范围的左边界
 * @param {number} r - 当前搜索范围的右边界
 * @param {number} k - 目标元素的索引（从 0 开始）
 * @return {number} - 数组中第 k 大的元素
 */
function quickselect(nums, l, r, k) {
  if (l === r) return nums[k] // 递归终止条件, 找到第 k 大的元素

  const x = nums[l] // 选择第一个元素作为枢轴
  let i = l - 1,
    j = r + 1

  // 快速排序的划分过程
  while (i < j) {
    do i++
    while (nums[i] < x) // 找到大于等于枢轴的元素
    do j--
    while (nums[j] > x) // 找到小于等于枢轴的元素

    // 交换 nums[i] 和 nums[j]
    if (i < j) {
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
    }
  }

  // 递归查找, 确定第 k 大元素的位置
  if (k <= j) {
    return quickselect(nums, l, j, k) // 第 k 大元素在左边
  } else {
    return quickselect(nums, j + 1, r, k) // 第 k 大元素在右边
  }
}