【NC207028】第k小数

题目

第k小数

快速排序思想

思路

这道题有多种解法，这里记录一种个人认为最优的解法：基于快速排序的选择算法

基于快速排序的寻找数组中第 k k k 小元素的算法也称为快速选择算法。它的基本思想是，利用快速排序中的 p a r t i t i o n partition partition 函数将数组划分为若干个子数组，其中第一个子数组中的元素都小于等于一个特定的值 p i v o t pivot pivot，而第二个子数组中的元素都大于 p i v o t pivot pivot。如果第一个子数组中的元素的个数小于 k k k，那么我们就在第二个子数组中寻找第 k − m k-m k−m 大的元素，其中 m m m 是第一个子数组中元素的个数。如果第一个子数组中的元素的个数大于等于 k k k，那么我们就在第一个子数组中寻找第 k k k 小的元素。

需要注意的是，基于传统的快速排序算法要在给定数据是随机的情况下性能才好，对于人为构造的数据（卡时间的数据）来说性能不好，所以这里的快速选择算法是将随机化改进为了双指针以适应各种数据。

代码

#include <stdio.h>

#define N 5000005

// 快读
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

/**
 * @brief 寻找数组中第k小的元素（k=0,1,2...)
 *
 * @param a 数组
 * @param start 起始位置（闭区间）
 * @param end 结束位置（闭区间）
 * @param k 第k小的元素（k=0,1,2...)
 * @return int 第k小的元素本身
 */
int quick_select(int* a, int start, int end, int k) {
    if (start == end) return a[start];
    int pivot = a[start], i = start - 1, j = end + 1;
    while (i < j) {
        do i++;
        while (a[i] < pivot);
        do j--;
        while (a[j] > pivot);
        if (i < j) {
            a[i] ^= a[j];
            a[j] ^= a[i];
            a[i] ^= a[j];
        }
    }
    if (k <= j) return quick_select(a, start, j, k);
    return quick_select(a, j + 1, end, k);
}

int main(void) {
    int t = 0;
    scanf("%d", &t);
    int n = 0, k = 0;
    int a[N], i = 0;
    while (t--) {
        scanf("%d%d", &n, &k);
        for (i = 0; i < n; i++) {
            a[i] = read();
        }
        printf("%d\n", quick_select(a, 0, n - 1, k - 1));
    }
    return 0;
}