数组中的第K个最大元素 题目描述 ：给定整数数组 nums 和整数 k ，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。例如， nums = [3,2,1,5,6,4] ， k = 2 时，第2大的元素是 5 。 解题思路 ： 问题分析 直接排序后取第 k 个最大元素（即索引 n-k ）的时间复杂度为 O(n log n)，但我们可以用更高效的方法（如快速选择算法）将时间复杂度优化到平均 O(n)。 快速选择算法 基于快速排序的 分治思想 ，但每次只递归处理目标所在的一侧。 步骤： a. 随机选择一个基准值（pivot），将数组分为三部分：大于 pivot、等于 pivot、小于 pivot。 b. 若第 k 大元素在大于 pivot 的部分，则递归处理该部分；若在等于 pivot 的部分，直接返回 pivot；否则递归处理小于 pivot 的部分。 举例说明 以 nums = [3,2,1,5,6,4] , k=2 为例： 第一轮选 pivot=3，分区后：大于3的 [ 5,6,4]；等于3的 [ 3]；小于3的 [ 2,1 ]。 第2大的元素应在较大的部分（因为较大部分长度=3 ≥ k=2），递归处理 [ 5,6,4 ]。 第二轮选 pivot=5，分区后：大于5的 [ 6]；等于5的 [ 5]；小于5的 [ 4 ]。 较大部分长度=1 < k=2，说明目标在等于或小于部分。此时 k 需更新为 k-1=1 ，递归处理 [ 5,4 ]？实际上应重新判断：因为较大部分只有1个元素，第2大元素应是较大部分的第1大（即6）或等于部分？这里需注意：第k大是针对整个数组的，而递归时我们只关注当前子数组的相对顺序。 算法细节 分区时使用三路快排的思想，将数组分为 [大于pivot] [等于pivot] [小于pivot] 。 设较大部分长度为 L ，等于部分长度为 M ： 若 k ≤ L ，目标在较大部分，递归该部分。 若 L < k ≤ L + M ，目标在等于部分，直接返回 pivot。 若 k > L + M ，目标在较小部分，递归较小区间并更新 k = k - (L + M) 。 复杂度分析 平均时间复杂度 O(n)，最坏情况 O(n²)（可通过随机化pivot避免）。 空间复杂度 O(log n)（递归栈）。 通过这种分治策略，我们避免了完全排序，从而高效找到第 k 大元素。