跳到主要内容

AcWing 786. 第 k 个数

本节目标

用快速选择按一基排名定位第 k 小元素，只递归目标所在分区。

这道题复用排序与选择的分区，但目标不是完整排序，而是找到排序后排名第 k 的数。

查看 AcWing 原题

题意与约束​

给定 n 个整数和 k，其中 k 是一基排名：k = 1 表示最小值，k = n 表示最大值。重复值按出现次数占据多个排名。

朴素思路与瓶颈​

完整排序后读取第 k - 1 个位置需要 O(n log n)，却额外确定了其余所有元素的次序。快速选择只借助分区判断目标排名在哪一侧，并丢弃另一侧，期望时间降为 O(n)。

分区后留下哪一侧​

使用与快速排序相同的双指针分区。结束后分界位置为 pos，左段 [left, pos] 的长度是 leftLen，其中的每个值都不大于右段值。

  • 若 k <= leftLen，第 k 小仍在左段；
  • 否则答案在右段，右段内部的排名变为 k - leftLen。

被丢弃的一侧不可能包含答案，因此无需像快速排序那样递归两侧。每次只保留一侧，期望工作量为线性级。

代码实现​

C++ 将输入规模 n 和主数组 nums 放在全局作用域，核心函数 quickSelect(left, right, k) 只接收当前区间与一基排名并返回第 k 小值；分区交换会原地重排全局 nums，但不会保证整个数组最终有序。Python 的 quick_select(nums, k) 继续显式接收数组，也会原地分区。两种入口都只负责读取题目输入、调用核心函数并输出结果。

C++17
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int n;
vector<int> nums;

int partition(int left, int right) {
    const int pivot = nums[left + (right - left) / 2];
    int i = left - 1;
    int j = right + 1;
    while (true) {
        do {
            i++;
        } while (nums[i] < pivot);
        do {
            j--;
        } while (nums[j] > pivot);
        if (i >= j) {
            return j;
        }
        swap(nums[i], nums[j]);
    }
}

int quickSelect(int left, int right, int k) {
    if (left == right) {
        return nums[left];
    }

    const int pos = partition(left, right);
    const int leftLen = pos - left + 1;
    if (k <= leftLen) {
        return quickSelect(left, pos, k);
    }
    return quickSelect(pos + 1, right, k - leftLen);
}

int main() {
    int k;
    cin >> n >> k;
    nums.resize(n);
    for (int& x : nums) {
        cin >> x;
    }
    cout << quickSelect(0, n - 1, k);
    return 0;
}

复杂度分析​

  • 平均时间复杂度：O(n)，每次只进入一个分区。
  • 最坏时间复杂度：O(n²)，分区持续极不平衡时发生。
  • 额外空间复杂度：平均为 O(log n) 的递归栈。

易错点​

  • 把一基的 k 直接当成数组下标。
  • 进入右段后忘记减去左段长度。
  • 分区后仍递归两侧，退化回完整快速排序。

模式迁移​

第 k 小、第 k 大和中位数都可先统一成排名选择。只要分区能确定目标不在某一侧，就应立即丢弃那一侧。