A5552.二路归并 题解

UPD:后面更新了归并。

思路

总体思路第一步都是把两个数组合并成一个数组再排序，由于编者懒就先提一下。

且：令 $s → n+m$。

方法 1

map 红黑树键值会自动排序，让他帮我排就可以了，用的方法和桶是一样的。时间复杂度 $O(s \log s)$。

方法 2

就是两个序列合起来再用 STL 的 sort 排序（这里排序也可以是其他的），输出就可以了。时间复杂度 $O(s \log s)$。

方法 3

桶排，用桶记一下然后输出。时间复杂度 $O(s)$。

方法 4

堆排，用 STL 的优先队列（priority_queue）来排，记住 STL 的优先队列默认是大根堆，要手动切换成小根堆。时间复杂度 $O(s \log s)$。

方法 5

归并，按照归并排序的思路做，建议做做瑞士轮。时间复杂度 $O(s)$。

代码

挺简单的。

方法 1

#include <iostream>
#include <map>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	map<int,int> a;
	for (int i=0;i<n+m;++i){
		int t;
		cin >> t;
		++a[t];
	}
	for (const auto &item : a){
		for (int i=0;i<item.second;++i){
			cout<<item.first<<' ';
		}
	}
	cout<<endl;
	return 0;
}

方法 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	n+=m;
	vector<int> a;
	for (int i=0;i<n;++i){
		int t;
		cin >> t;
		a.emplace_back(t);
	}
	sort(a.begin(),a.end());
	for (const auto &item : a){
		cout<<item<<" ";
	}
	cout<<endl;
	return 0;
}

方法 3

#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	n+=m;
	vector<int> a(30001,0);
	int mx=-1;
	for (int i=0;i<n;++i){
		int t;
		cin >> t;
		++a[t];
		mx=max(mx,t);
	}
	for (int i=0;i<=mx;++i){
		for (;a[i];--a[i]){
			cout<<i<<" ";
		}
	}
	return 0;
}

方法 4

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	n+=m;
	priority_queue<int,vector<int>,greater<int>> a;
	for (int i=0;i<n;++i){
		int t;
		cin >> t;
		a.emplace(t);
	}
	while (!a.empty()){
		cout<<a.top()<<" ";
		a.pop();
	}
	return 0;
}

方法 5

#include <iostream>
#include <vector>
using namespace std;
void merge(const int n,const int m,const vector<int> &a,const vector<int> &b){
	int i=0,j=0;
	while (i<n && j<m){
		if (a[i]<=b[j]){
			cout<<a[i++]<<" ";
		}else{
			cout<<b[j++]<<" ";
		}
	}
	while (i<n){
		cout<<a[i++]<<" ";
	}
	while (j<m){
		cout<<b[j++]<<" ";
	}
}
int main(){
	int n,m;
	cin >> n >> m;
	vector<int> a(n),b(m);
	for (int i=0;i<n;++i){
		cin >> a[i];
	}
	for (int i=0;i<m;++i){
		cin >> b[i];
	}
	merge(n,m,a,b);
	return 0;
}