寻找数组中的第K大元素（基于快速选择算法）

题目描述
给定一个未排序的整数数组和一个整数k，要求找出数组中第k大的元素。注意，第k大指的是从大到小排序后的第k个元素。例如，在数组[3,2,1,5,6,4]中，第2大的元素是5。

解题思路
最直接的方法是先对数组进行排序（如快速排序），然后直接取第k大的元素。但排序的时间复杂度为O(n log n)，而使用快速选择算法（QuickSelect）可以将平均时间复杂度优化到O(n)。

快速选择算法是快速排序的变种，其核心思想是“分治”：

1. 在数组中随机选择一个元素作为“基准”（pivot）。
2. 将数组划分为两部分：比基准大的元素放在左侧，比基准小的元素放在右侧（注意：这里为了找第k大，需按降序划分）。
3. 根据基准的位置与k的关系，递归地在左侧或右侧子数组中继续查找。

步骤详解

步骤1：划分函数（Partition）的设计
划分函数的目标是将数组重新排列，使得所有大于基准的元素位于基准左侧，小于基准的元素位于右侧。返回基准的最终位置。

示例步骤（以降序为例）：

1. 选择最右侧元素作为基准（pivot = nums[right]）。
2. 初始化指针i指向起始位置（i = left）。
3. 遍历数组从left到right-1，若当前元素大于基准，则将其与指针i处的元素交换，并让i右移。
4. 最后将基准（nums[right]）与i位置的元素交换，返回i。

def partition(nums, left, right):
    pivot = nums[right]  # 选择最右侧元素为基准
    i = left
    for j in range(left, right):
        if nums[j] > pivot:  # 注意：找第k大时按降序划分
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[right] = nums[right], nums[i]
    return i  # 返回基准的最终位置

步骤2：快速选择递归逻辑

1. 调用划分函数，得到基准的位置pos。
2. 比较pos与k-1（因为第k大在排序后下标为k-1）：
   • 若pos == k-1，则nums[pos]即为所求。
   • 若pos < k-1，说明第k大在右侧子数组（nums[pos+1: right]），递归处理右侧。
   • 若pos > k-1，说明第k大在左侧子数组（nums[left: pos]），递归处理左侧。

def quick_select(nums, left, right, k):
    if left <= right:
        pos = partition(nums, left, right)
        if pos == k - 1:
            return nums[pos]
        elif pos < k - 1:
            return quick_select(nums, pos + 1, right, k)
        else:
            return quick_select(nums, left, pos - 1, k)

步骤3：处理边界情况

• 若k超出数组范围（如k > len(nums)），需提前判断。
• 递归基线条件为left <= right。

完整代码示例

def findKthLargest(nums, k):
    def partition(left, right):
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] > pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

    def select(left, right, k):
        if left <= right:
            pos = partition(left, right)
            if pos == k - 1:
                return nums[pos]
            elif pos < k - 1:
                return select(pos + 1, right, k)
            else:
                return select(left, pos - 1, k)

    return select(0, len(nums) - 1, k)

# 测试
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(findKthLargest(nums, k))  # 输出5

复杂度分析

• 平均时间复杂度：O(n)。每次划分平均减少一半的搜索范围，n + n/2 + n/4 + ... ≈ 2n。
• 最坏时间复杂度：O(n²)。当基准总是选到最小或最大元素时，每次只能减少一个元素。
• 优化策略：可随机选择基准（在划分前交换随机元素到最右侧），避免最坏情况。

对比其他方法

• 排序法：O(n log n)，简单但效率低。
• 堆法：维护一个大小为k的小顶堆，遍历数组后堆顶即为第k大元素，时间复杂度O(n log k)。