求第$k$大数

原文链接

问题

在一组数中，求其第$k$大数

分析

方法一 排序

可以使用排序算法对原数组进行排序，然后取出其下标为$k$的数即为第$k$大数。

时间复杂度

其时间复杂度与所使用的排序算法有关，如归并排序或者快速排序其复杂度为$O(nlogn)$

方法二 堆

根据原数组建小根堆，依次弹出$k$次堆顶，其第$k$次弹出的数即为第$k$大数。

时间复杂度

其时间复杂度是$O(klogn)$(弹出堆顶的复杂度是$O(logn)$, 共需弹出$k$次)。该方法明显优于直接使用排序。

方法三 依据快速排序的思想

在快速排序算法中，一个重要的操作是partition操作, partition选取一个枢轴点，将其放入合适的位置，使其左边均小于等于它，右边均大于它。

执行完partition操作后，设左边的长度为$L$, 枢轴点的位置为$p$(将枢轴元素视为属于左部即$p==L$)

• 若$L==k$，则枢轴点$v$即为第$k$大数
• 若$k<L$, 则在左部求其第$k$大数
• 若$k>L$, 则在右部求其第$k-L$大数

时间复杂度

若使用随机化快排算法，则每次partition的划分期望是等分，而且每次只对一半的数据进行递归求解, 因此其时间复杂度为
$$O\left(\sum n+\frac{n}{4}+\frac{n}{8}+\cdots +1\right)=O(2n)=O(n)$$
可见该算法可在$O(n)$的时间内找到任意第$k$数

编码实现

#include <iostream>
#include <ctime>
using namespace std;

int partition(int data[], int l, int r) {
    // 初始化种子
    srand((unsigned)time(nullptr));
    // 随机选取枢轴元素
    swap(data[l], data[rand() % (r - l + 1) + l]);
    int v = data[l];
    // [l+1, i] <= v, [j, r) >= v
    int i = l + 1, j = r;
    while (true) {
        // 依次找到两边不满足的元素，交换
        while (i <= r && data[i] < v) i++;
        while (j >= l + 1 && data[j] > v) j--;
        if (i > j) break;
        swap(data[i], data[j]);
        i++;
        j--;
    }
    std::swap(data[l], data[j]);
    return j;
}
int fastSearchKNum(int data[], int l, int r, int k) {
    int p = partition(data, l, r);
    // 包含枢轴点的左部长度
    int L = p - l + 1;
    if (L == k) { // 情况1 枢轴元素即为第k大元素
        return data[p];
    } else if (k < L) { // 情况2 第k大元素在左部
        return fastSearchKNum(data, l, p - 1, k);
    } else { // 情况3 第k大元素在右部
        return fastSearchKNum(data, p + 1, r, k - L);
    }
}

int main() {
    int data[] = {5, 4, 3, 2, 1, 6, 8, 7, 10, 9};
    int k = 5;
    int kNum = fastSearchKNum(data, 0, 9, k);
    std::cout << "The " << k << "'th number is " << kNum  << std::endl;
    return 0;
}

输出

The 5'th largest number is 5