数据结构：topK 第K大数

阳光穿透心脏的1/2处 2022-05-31 12:54 160阅读 0赞

# 第K大数 #

这个是借助快速排序来做的，是快排的一个变形

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    int partition(int* a, int beg, int end);
    void quickSort(int* a, int beg, int end);
    void print(int* a, int SIZE);
    
    
    //这是一个时间复杂度为O(n)的查找第k大数的算法
    //这叫选择问题,也是中位数问题
    //面试中可能问你能够早O(n)之内找到中位数吗?就是这个问题
    //这个算法的期望是O(n),最坏的情况是O(n*n)
    int RandomiezdSelect(int* a, int SIZE, int k);
    int getFirstKNum(int* a, int beg, int end, int k);
    
    int main()
    {
        srand(time(0));
        const int SIZE = 20;
        int * a = new int[SIZE];
        int * b = new int[SIZE];
        for (int i = 0; i<SIZE; i++)
            b[i] = a[i] = (int)(rand() % (2 * SIZE));
    
        cout << "QuickSort Before: " << endl;
        print(a, SIZE);
        quickSort(a, 0, SIZE - 1);
        cout << "QuickSort After: " << endl;
        print(a, SIZE);
    
        for (int k = 1; k <= SIZE; k++)
        {
            //cout<<k<<"ed Num is "<<RandomiezdSelect(b,SIZE,k)<<endl;
            cout << RandomiezdSelect(b, SIZE, k) << " ";
        }
    
        delete a, b;
        system("pause");
        return 0;
    }
    
    // 这个问题借鉴了快速排序的算法思路,算法很容易理解,此处酒就不赘述了
    int getFirstKNum(int* a, int beg, int end, int k)
    {
        //这个表示数组只有一个元素了
        if (beg == end)
            return a[beg];
        else
        {
            //数组划分
            int mid = partition(a, beg, end);
            int len = mid - beg + 1;
    
            //找到第k大的数
            if (len == k)
                return a[mid];
            else if (len>k)   //注意和快速排序一样,是mid-1
                return getFirstKNum(a, beg, mid - 1, k);
            else            //注意和快速排序一样,是mid+1
                return getFirstKNum(a, mid + 1, end, k - len);
    
        }
    }
    
    int RandomiezdSelect(int* a, int SIZE, int k)
    {
        return getFirstKNum(a, 0, SIZE - 1, k);
    }
    
    void print(int* a, int SIZE)
    {
        for (int i = 0; i<SIZE; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    
    //这个过程很奇妙  ,要记着
    int partition(int* a, int beg, int end)
    {
        int first = beg;
        int last = end;
        int key = a[first];
        //first的位置就空出来了
        while (first<last)
        {
            //重后向前扫描
            while (first<last && a[last] >= key)
                last--;
            a[first] = a[last];
    
            //重前向后扫描
            while (first<last && a[first] <= key)
                first++;
            a[last] = a[first];
        }
        //这个时候first和last是相等的
        a[first] = key;
        return first;
    }
    
    void quickSort(int* a, int beg, int end)
    {
        if (beg<end)
        {
            int mid = partition(a, beg, end);
            //记着要mid-1 和mid+1
            quickSort(a, beg, mid - 1);
            quickSort(a, mid + 1, end);
        }
    }