区间内第K小元素查询（QuickSelect 算法）

题目描述
给定一个整数数组和一个区间 [L, R]，以及一个整数 K，要求快速找出该区间内第 K 小的元素（即排序后位于第 K 位的元素）。注意：K 从 1 开始计数（即第 1 小就是最小值）。例如，数组 [3, 2, 1, 5, 4] 在区间 [1, 3]（对应子数组 [2, 1, 5]）中，第 2 小的元素是 2。

解题思路

1. 朴素解法：提取区间内的子数组并排序，直接取第 K 个元素。时间复杂度为 O(n log n)，在多次查询时效率低。
2. 优化目标：利用快速排序的分区思想（Partition）实现平均 O(n) 的单次查询，即 QuickSelect 算法。

步骤详解

步骤 1：理解分区（Partition）操作

• 从区间 [L, R] 中随机选择一个元素作为“基准”（pivot）。
• 将区间内所有小于 pivot 的元素移到其左侧，大于 pivot 的元素移到右侧。
• 分区完成后，pivot 会位于其最终排序位置，记其索引为 p。

示例：
数组 [7, 2, 5, 1, 8]，区间 [0, 4]，选择 pivot=5（索引 2）：
分区后可能变为 [2, 1, 5, 7, 8]，此时 pivot=5 位于索引 2。

步骤 2：利用分区定位第 K 小元素
分区后，pivot 的索引 p 相对于区间起点 L 的位置为 pos = p - L + 1（即 pivot 是区间内第 pos 小的元素）。

• 若 pos == K：pivot 即为所求。
• 若 pos > K：第 K 小元素在左侧子区间 [L, p-1] 中，递归处理。
• 若 pos < K：第 K 小元素在右侧子区间 [p+1, R] 中，但需在右侧找第 K - pos 小的元素。

步骤 3：实现 QuickSelect 算法

import random

def quick_select(arr, L, R, K):
    if L == R:  # 区间只剩一个元素
        return arr[L]
    
    # 随机选择基准并分区
    pivot_idx = random.randint(L, R)
    p = partition(arr, L, R, pivot_idx)
    
    pos = p - L + 1  # pivot 在区间中的排名
    if pos == K:
        return arr[p]
    elif pos > K:
        return quick_select(arr, L, p - 1, K)  # 在左半部分找第 K 小
    else:
        return quick_select(arr, p + 1, R, K - pos)  # 在右半部分找第 (K-pos) 小

def partition(arr, L, R, pivot_idx):
    # 将基准交换到末尾
    arr[pivot_idx], arr[R] = arr[R], arr[pivot_idx]
    pivot_val = arr[R]
    # 双指针分区：i 指向小于基准的区间末尾
    i = L
    for j in range(L, R):
        if arr[j] < pivot_val:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    # 将基准放回正确位置
    arr[i], arr[R] = arr[R], arr[i]
    return i

步骤 4：示例演示
数组 [3, 2, 1, 5, 4]，查询区间 [1, 3]（子数组 [2, 1, 5]）的第 2 小元素：

1. 在子数组内运行 QuickSelect：
   • 随机选 pivot=1（值），分区后为 [1, 2, 5]，pivot 索引 p=1（相对整个数组），相对区间起点 L=1 的排名 pos=1。
   • 因 pos=1 < K=2，递归处理右子区间 [2, 3]（对应 [2, 5]），找第 2-1=1 小元素。
2. 在 [2, 5] 中选 pivot=2，分区后为 [2, 5]，排名 pos=1，恰好为所求，返回 2。

复杂度分析

• 平均时间复杂度：O(n)，因每次递归区间大小减半。
• 最坏情况：O(n²)（例如每次选到极值作为基准），但随机化 pivot 避免退化。
• 扩展：若需多次查询不同区间，可结合持久化线段树或划分树（如 O(log n) 查询的算法）。