区间内第K大元素查询（基于快速选择算法的变种）

题目描述
给定一个整数数组和多个查询，每个查询包含三个参数：区间左边界L、区间右边界R和整数K。要求返回每个查询区间[L,R]内第K大的元素值。注意是第K大（从大到小排序后的第K个），而不是第K小。

解题过程

1. 问题分析

   • 直接思路：对每个查询区间内的子数组排序，然后取第K个元素。时间复杂度为O(Q * n log n)，其中Q是查询次数，n是数组长度。当Q或n较大时效率很低。
   • 核心挑战：如何高效处理多个区间查询，避免每次都对子数组排序。

2. 快速选择算法回顾

   • 快速选择是快速排序的变种，用于在未排序数组中查找第K小（或第K大）元素，平均时间复杂度O(n)。
   • 步骤：
     a. 随机选择基准元素（pivot）
     b. 将数组划分为小于、等于、大于基准的三部分
     c. 根据K值所在范围，递归在相应分区继续查找

3. 区间查询的特殊性

   • 难点：我们需要在数组的任意子区间内进行查询，而不是整个数组。
   • 关键观察：如果对每个查询都复制子数组再应用快速选择，复制操作本身就需要O(n)时间。

4. 改进思路：原地分区

   • 不复制子数组，而是直接在原数组的[L,R]区间内进行分区操作。
   • 分区时，我们只处理区间内的元素，但需要记录这些元素的原始位置。

5. 详细步骤
   a. 对于每个查询[L,R,K]：

   • 初始化left = L, right = R
     b. 在区间内随机选择基准元素pivot_index
     c. 将pivot交换到区间末尾（位置R）
     d. 初始化分区指针store_index = left
     e. 遍历区间[left, R-1]：
   • 如果当前元素大于pivot（因为找第K大），将其交换到store_index位置，然后store_index++
     f. 将基准元素从末尾交换到store_index位置
     g. 计算基准的排名rank = store_index - L + 1
     h. 比较rank与K：
   • 如果rank == K：返回基准元素
   • 如果rank > K：在左子区间[L, store_index-1]中找第K大
   • 如果rank < K：在右子区间[store_index+1, R]中找第(K-rank)大

6. 时间复杂度分析

   • 平均情况：O(n) per query（n为区间长度）
   • 最坏情况：O(n²) per query（当基准总是选到最值）
   • 优化：使用三数取中法选择基准，避免最坏情况

7. 进一步优化考虑

   • 对于多个查询，可以考虑预处理（如建立线段树存储排序信息）
   • 但更复杂的预处理（如持久化线段树）会增加实现难度
   • 当前方法在查询次数不多时是实际可行的选择

关键点总结

• 将快速选择算法适配到任意区间
• 分区操作时保持元素相对位置不变
• 通过排名比较确定递归方向
• 注意第K大与第K小的分区逻辑区别（大于基准放左边）