【数字之魅】寻找最大的K个数(求第k大的数)

悠悠 2022-08-09 05:14 179阅读 0赞

**前言：编程之美上并没有给出实际的代码，这里我参考yoona博主的做法自己也写了一遍，并记录下来。**  
与此相似的题目是：  
\- 求第k大的数  
\- 求第k小的数  
这里给出比较好的两个做法，分别是快排思想和堆思想，至于怎么做的这里就不重述了，直接上代码。

## 快排思想解 ##

int quicksort_cut(int arr[],int left,int right)
    {
        if (arr == NULL || left >= right)
        {
            return -1;
        }
        int i,j,temp;
        i = left;   j = right;
        temp = arr[left];
        while(i<j)
        {
            while(temp > arr[j] && i < j)
                j--;
            if (i<j){
                arr[i] = arr[j];
                i++;
            }
            while(temp <= arr[i] && i < j)
                i++;
            if (i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        //此时 i==j
        arr[i] = temp;
        return i;
    }
    
    int get_k_bigs(int arr[],int left,int right,int k)
    {
        int cut_index,n;
        if (left >= right || arr == NULL)
        {
            return -1;
        }
        //划分，返回划分位置.
        cut_index = quicksort_cut(arr,left,right);
        n = cut_index - left +1;
        if (k == n)
        {
            return cut_index;
        }
        else if (n<k) //如果小于k个，还要在右边拿k-n个
        {
            return get_k_bigs(arr,cut_index+1,right,k-n);
        }
        else //如果大于k个，则范围缩小为left--cut_index
        {
            return get_k_bigs(arr,left,cut_index,k);
        }
    }

测试代码：

int main()
    {
        int a[] = {
       4,5,1,6,2,7,3,8};  
        vector<int>* result;
        int x = get_k_bigs(a,0,7,4);
        result = new vector<int>(a,a+x+1);
        for (vector<int>::iterator iter = result->begin();iter != result->end();iter++)
        {
            cout << *iter << " ";
        }
        cout << endl;
        delete result;
        system("pause");
        return 0;
    }

## 堆思想解. ##

> 用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆，因为这个元素比最大的K个数要小。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。  
> 当数据量很大时（这时候数据已经不能全部装入内存，所以要求尽可能少的遍历数组）可以采用这种方法。

实现：

//index：调整的堆节点；n：堆元素个数;该函数只调整一个节点。
    //index，必须是从1开始算起。
    void min_heap_shift(int a[],int index,int n){  
        int i,j,temp,finished;
        temp = a[index];
        i = index;
        j = i*2;    //i的子节点
        finished = 0;
        while(j<=n && !finished)
        {
            if (a[j] > a[j+1] && j < n)
                j++;
            if (temp <= a[j])
            {
                finished = 1;
            }
            else
            {
                a[i] = a[j];
                i = j;
                j = 2*i;
            }
        }
        a[i] = temp;
    }  
    
    
    /*
    *   建堆：将一个数组a[1~k]变成一个最小堆  
    *   避免额外空间，就在原来数组中建
    */
    void build_min_heap(int a[],int k){  
        int i;  
        for(i = k/2;i >= 1;i--){  
            min_heap_shift(a,i,k);  
        }  
    }  
    /*
    *注意arr是从1开始的。
    *k表示要提取的最大的k个数
    *n表示a数组从1开始的长度
    */
    void get_k_bigs(int a[],int k,int n)
    {
        if (a == NULL || k>n)
        {
            return;
        }
        int i;
        build_min_heap(a,k);
        for (i = n;i>k;i--)
        {
            if (a[1] < a[i])
            {
                a[1] ^= a[i];
                a[i] ^= a[1];
                a[1] ^= a[i];
                min_heap_shift(a,1,k);
            }
        }
    }

测试代码：

int main()
    {
        int n = 6;  
        int k = 3;  
        //a[0]不用，堆的根结点是从1开始的  
        int a[] = {
       0,3,17,8,27,7,20};  
        get_k_bigs(a,k,n);
        for(int i = 1;i <= k;i++){  
            printf("%d ",a[i]);  
        } 
        system("pause");
        return 0;
    }

## 总结 ##

其实，这道题给我的感触是蛮深的，知识的迁移，知识的灵活应用，都是很好的锻炼，最基本的锻炼了我对快排和堆排的理解。  
最后，感谢（[http://blog.csdn.net/sunnyyoona/article/details/26380473][http_blog.csdn.net_sunnyyoona_article_details_26380473]）这篇博文讲述！

[http_blog.csdn.net_sunnyyoona_article_details_26380473]: http://blog.csdn.net/sunnyyoona/article/details/26380473