Top K问题 —— 第K个最大的数

第K个最大的数

这种题目第一种想法就是直接排序，再去找第K个最大的数，但因为又排序的存在，时间复杂度就无法直接保证。这里写一种时间复杂度为O(n)的算法。

思想是快速排序的思想，但是不去完全排序 （快排了，但没有完全快排） 选一个枢轴点，用快排的方法将数组分为两部分，位于枢轴点左边的数都比它大，位于枢轴点右边的数都比它小。

1.如果枢轴点的索引刚好是k-1,则此时它对应的就是数组的第k大的数；
2.如果比k-1大，那么第k大的数位于它的左边部分；
3.如果比k-1小，那么第k大的数位于它的右边部分；

#include <iostream>

using namespace std;
int Data[100];

int Quick_sort(int* a, int low, int high)        //只做一次快速排序
{
    int key = a[low];
    while (low < high)
    {
        while (key <= a[high] && low < high)
            high--;
        a[low] = a[high];
        while (key >= a[low] && high > low)
            low++;
        a[high] = a[low];
    }
    a[high] = key;
    return high;
}


int Select_k(int* a, int low, int high, int k)          //找第k个最大的数
{
    int index;
    if (low == high) return a[low];
    int partition = Quick_sort(a, low, high);
    index = high - partition + 1;                  //找的是第index个最大值
    if (index == k) return a[partition];
    else if (index < k) return Select_k(a, low, partition - 1, k - index);   //小于k，在左半部找（相对于index的位置为k-index)
    else if (index > k) return Select_k(a, partition + 1, high,  k);        //大于k,在左半部找(无相对位置，找第k个）
}

int main()
{
    const int lenth = 10;
    cout << "输入数组元素(10个元素）：" << endl;
    for (int i = 1; i <= lenth; i++)
        cin >> Data[i];
    cout << "输入k: " << endl;
    int k; cin >> k;
    int kth_top = Select_k(Data, 1, lenth, k);
    cout << "第"<<k<<"个最大的数为：" << kth_top << endl;
    return 0;
}

运行结果：