首页 > 代码库 > N个降序数组，找到最大的K个数
N个降序数组，找到最大的K个数
问题定义
这个问题来自网上看到的百度算法题，感觉很不错，问题定义如下：
假定有20个有序数组，每个数组有500个数字，降序排列，数字类型32位uint数值，现在需要取出这10000个数字中最大的500个，怎么做？
解决方法
这里其实有很多解决方法，笨拙的或者巧妙的。这里介绍一个非常不错的方法，使用最大堆堆排序：
1. 建立大顶堆，维度为数组的个数，这里为20（第一次 插入的是每个数组中最大的值，即第一个元素）。
2. 删除最大堆堆顶，保存到数组或者栈中，然后向最大堆插入删除的元素所在数组的下一个元素。
3. 重复第1,2个步骤，直到删除个数为最大的K个数，这里为500.
代码：
#include <iostream>#include <cstdlib>#include <algorithm>#include <queue>#include <functional> using namespace std;#define ROWS 20#define COLS 500int 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;}
题外话：
上面的是有序数组，但是如果是无序数组呢，可以建立维度为K（这里为500）的最小堆，然后每次删除最小堆的堆顶，直到遍历完所有的数，剩下的就是所求的最大K个数。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。