N个降序数组，找到最大的K个数

以你之姓@ 2022-08-21 01:11 138阅读 0赞

# [N个降序数组，找到最大的K个数][N_K] #

### 问题定义 ###

这个问题来自网上看到的百度算法题，感觉很不错，问题定义如下：

假定有20个有序数组，每个数组有500个数字，降序排列，数字类型32位uint数值，现在需要取出这10000个数字中最大的500个，怎么做？

### 解决方法 ###

这里其实有很多解决方法，笨拙的或者巧妙的。这里介绍一个非常不错的方法，使用最大堆堆排序：

1. 建立大顶堆，维度为数组的个数，这里为20（第一次 插入的是每个数组中最大的值，即第一个元素）。

2. 删除最大堆堆顶，保存到数组或者栈中，然后向最大堆插入删除的元素所在数组的下一个元素。

3. 重复第1,2个步骤，直到删除个数为最大的K个数，这里为500.

### 代码： ###

![复制代码][copycode.gif]

#include <iostream>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <functional> 
    using namespace std;
    
    #define ROWS 20
    #define COLS 500
    
    int data[ROWS][COLS];
    
    void CreateData()
    {
        for(int i=0; i<ROWS; i++)
        {
            for(int j=0; j<COLS;j++)
            {
                data[i][j] = rand();                         //生成随机元素
            }
        }
        for( int i=0; i<ROWS; i++)
            sort(data[i],data[i]+COLS, greater<int>());     //对每一行降序排列
    }
    
    struct Node 
    {
        int *p;  //指向某个列，因为要放入优先队列中，所以要比较大小，就用结构体封装了下
        bool operator<(const struct Node &node) const
        {
            return *p < *node.p;
        }
    };
    
    void OutMinData( int k)
    {
        struct Node arr[ROWS];
        for(int i=0; i<ROWS;i++)
        {
            arr[i].p = data[i];                       //初始化指针指向各行的首位
        }
        priority_queue<Node > queue( arr, arr+ROWS );  //使用优先队列，默认是大堆
    
        for( int i=0; i<k&&i<COLS; i++)                //算法核心就是这个循环
        {
            Node temp = queue.top();                   //取出队列中最大的元素
            cout << *temp.p << " " <<endl;            
            queue.pop();                               //从队列里删除    
            temp.p++;                                  //对应行的指针后移
            queue.push( temp );                        //这里面有log（ROWS）次操作，所以算法的总复杂度为O（klog（20））
        }
        
    }
    
    int main()
    {
        CreateData();  //生成数据
        int k=500;
        OutMinData( k ); //输出k个元素，这里k不要大于列数COL，可以改进，去掉这个限制，不过会让程序不好懂，就没加
        return 0;
    }

![复制代码][copycode.gif]

题外话：

上面的是有序数组，但是如果是无序数组呢，可以建立维度为K（这里为500）的最小堆，然后每次删除最小堆的堆顶，直到遍历完所有的数，剩下的就是所求的最大K个数。

[N_K]: http://www.cnblogs.com/ywl925/p/3794852.html
[copycode.gif]: /images/20220731/5e674b08ae434d2b934b42521e3205eb.png