题解

本题要求在 O(n) 时间复杂度内找到第 k 个最大的元素，适合使用 快速选择算法（QuickSelect）。快速选择是一种类似快速排序的算法，使用 分区（Partition） 思想，可以在 O(n) 的期望时间复杂度下找到第 k 大的元素。

思路

1. 选择一个 基准元素（pivot） 进行 分区（Partition）：
   • 所有大于 pivot 的元素放在左侧；
   • 所有小于 pivot 的元素放在右侧；
   • pivot 归位，确定其在 排序后的位置。
2. 递归进行：

Leetcode 74.数组中的第K个最大元素-原题链接

题目

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

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

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

输入

• 第一行输入 n 和 k，其中：
  • n 代表数组长度 （1 ≤ n ≤ 10⁵）
  • k 代表要找到的第 k 个最大元素 （1 ≤ k ≤ n）
• 第二行输入 n 个整数，表示数组 nums （-10⁴ ≤ nums[i] ≤ 10⁴）

输出

• 输出数组 nums 中第 k 个最大的元素。

样例输入 1

6 2
3 2 1 5 6 4

样例输出 1

5

样例输入 2

9 4
3 2 3 1 2 4 5 5 6

样例输出 2

4