洛谷：P1923：求第k小的数

题目

P1923：求第k小的数

分析

这道题当然有偷懒的解法，那就是用内置的sort排序后直接输出第k小的数字。

还是用我们之前讲过的快速排序思路。

1. 选择一个哨兵位置：guard = nums[(l + r) / 2]。这里我们更关心元素的位置（下标），而不是具体值。
2. 初始化左右指针：int left = l, right = r。
3. 在left <= right的条件下，从左侧找到第一个大于guard的元素，从右侧找到第一个小于guard的元素。
4. 此时，如果left <= right，那么交换这两个数值，并继续缩小左右指针范围。

上述循环结束时，必然有：left > right，也就是左右指针出现了交叉。

如果：

1. 如果k <= right，说明第k小的元素位于左区间，递归在[l, right]中查找。
2. 如果k >= left，说明第k小的元素位于右区间，递归在[left, r]中查找。
3. 如果right < k < left，说明第k小的元素恰好等于当前哨兵值guard，可以直接返回guard。这是因为循环结束时有left = right + 1；当k落在两者之间时，说明k正好指向分界位置的元素，其值等于guard。

答案

思考

本题建议读者掌握，而不是偷懒解决。

另外，find_nth函数的签名比较复杂，我这样设计是为了避免使用全局变量，这只是我的个人偏好。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, res;
    cin >> n >> k;

    vector<int> numbers(n);

    for (int i = 0; i < n; i++)
    {
        cin >> numbers[i];
    }

    sort(numbers.begin(), numbers.end());
    cout << numbers[k];

    return 0;
}

最后，提醒一下：建议把下面这两行放在main()开头，否则在输入数据量较大的时候可能会超时。我这边的情况是2个AC，3个TLE；加入输入优化后就全部AC了。

ios_base::sync_with_stdio(false);
cin.tie(NULL);