android开发实战 ScrollView Jetson Nano less kubernetes cakephp awk safari jqgrid Web Uploader 郑州网络 nodejs教程视频 多商户商城模板 jquery事件绑定 jquery关闭当前窗口 python正则表达式 mysql建表 mysql入门 python类 pythonapi javatrim java学习手册 java课程学习 java面向对象 java重命名 java注释规范 自动喊话器 dll之家 kontakt iar下载 dxsetup 3d看图软件 大势至usb监控 英雄联盟设置 bz2解压 qq农场图标 igfxtray 神牧属性 mac办公软件 php完全自学手册
当前位置: 首页 > 学习教程  > 编程语言

面试题:合并k个有序数组

2020/10/8 19:10:39 文章标签:

一般来说 ,可能k有序数组的元素个数不一定。(假设有序数组从小到大) 思路如下 , 建立大小为k的小根堆,刚开始取k个数组的头结点放入堆中。**后面我们用堆顶元素来源的数组的下一个元素进行替换。**每次将堆顶元素存入结vector ret中。 注意&a…

一般来说 ,可能k有序数组的元素个数不一定。(假设有序数组从小到大)
思路如下 , 建立大小为k的小根堆,刚开始取k个数组的头结点放入堆中。**后面我们用堆顶元素来源的数组的下一个元素进行替换。**每次将堆顶元素存入结vector ret中。
注意:
1。显然我们需要确定堆顶元素来自于哪个数组,设置标志即可
2。当某一个数组元素为空时(已经取完了)。就不用向堆中替换了

代码如下

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

typedef struct Node
{
	int val;
	int col;
	int row;
	Node(int _val, int _row, int _col)
		:val(_val)
		, row(_row)
		, col(_col)
	{}
}newNode;


struct compare
{
	bool operator()(Node node1, Node node2)
	{
		return node1.val > node2.val;//这是小根堆
	}
};
vector<int> MergeArrays(vector<vector<int>>& arrs)
{
	vector<int> res;
	priority_queue<Node, vector<Node>, compare> pq;
	for (size_t i = 0; i < arrs.size(); ++i)
	{
		Node node(arrs[i][0], i, 0);
		pq.emplace(node);//涉及到了移动语义,局部变量也要好好利用。
	
	}
	//先将堆中元素排序

	while (!pq.empty())//堆里面还有数据
	{
		//将堆顶元素(最小值)插入到结果数组中
		Node temp_node = pq.top();
		res.push_back(temp_node.val);
		pq.pop();
		//开始像堆中添加元素。判断堆顶元素是不是其数组的最后一个元素
		if (temp_node.col == arrs[temp_node.row].size() - 1)
		{
		//已经是某一行中的最后一列了。不用添加进去了  
			continue;
		}
		else
		{
			Node node(arrs[temp_node.row][temp_node.col+1], temp_node.row, temp_node.col + 1);//将同行的下一个元素放入列中
			pq.emplace(node);//涉及到了移动语义,局部变量也要好好利用
		}
	
	}
	return res;
}
int main()
{
	vector<vector<int>> arrs{ {1,2,7,9}, {5,6}, {3}, {4,8} };
	//vector<vector<int>> arrs{ {1,2,},  {4} };
	vector<int> res = MergeArrays(arrs);
	for (auto c : res)
		cout << c << " ";
	cout << endl;
	return 0;
}

里面我为什么使用emplace 而不用push_back 这是为了避免不必要的内存拷贝。这里涉及了移动语义(面试被问过)的知识,大家有兴趣可以看看c++11的新特性。


本文链接: http://www.dtmao.cc/news_show_250099.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?