0215. 数组中的第K个最大元素【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 快速选择

1. 📝 题目描述

• leetcode

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

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

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

---

示例 1：

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

示例 2：

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

---

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

2. 🎯 s.1 - 快速选择

c

void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }

int quickSelect(int* nums, int lo, int hi, int target) {
    int pivot = nums[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (nums[j] <= pivot) swap(&nums[i++], &nums[j]);
    }
    swap(&nums[i], &nums[hi]);
    if (i == target) return nums[i];
    if (i < target) return quickSelect(nums, i + 1, hi, target);
    return quickSelect(nums, lo, i - 1, target);
}

int findKthLargest(int* nums, int numsSize, int k) {
    return quickSelect(nums, 0, numsSize - 1, numsSize - k);
}

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const target = nums.length - k
  function quickSelect(lo, hi) {
    const pivot = nums[hi]
    let i = lo
    for (let j = lo; j < hi; j++) {
      if (nums[j] <= pivot) {
        ;[nums[i], nums[j]] = [nums[j], nums[i]]
        i++
      }
    }
    ;[nums[i], nums[hi]] = [nums[hi], nums[i]]
    if (i === target) return nums[i]
    if (i < target) return quickSelect(i + 1, hi)
    return quickSelect(lo, i - 1)
  }
  return quickSelect(0, nums.length - 1)
}

py

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k
        def quick_select(lo, hi):
            pivot, i = nums[hi], lo
            for j in range(lo, hi):
                if nums[j] <= pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[hi] = nums[hi], nums[i]
            if i == target:
                return nums[i]
            elif i < target:
                return quick_select(i + 1, hi)
            else:
                return quick_select(lo, i - 1)
        return quick_select(0, len(nums) - 1)

• 时间复杂度：平均 $O(n)$，最坏 $O(n^2)$
• 空间复杂度：$O(\log n)$，递归栈平均深度

算法思路：

• 第 $k$ 大等价于升序后索引 $n-k$ 的元素
• 使用快速选择算法，每次 partition 后根据 pivot 位置决定往左还是往右继续搜索