【题解】合并有序表
【题目描述】
k路归并问题
把k个有序表合并成一个有序表。
元素共有n个。
【输入描述】
读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数，表示第i个序列。
总数小于100000。
【输出描述】
输出有序序列
【样例输入】
6 3 1 2 3 3 4 5 6 3 7 10 13 3 8 11 14 3 9 12 15 3 0 16 17
【样例输出】
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
【题目分析】
核心方法
把所有数字全部存到一个大数组里（不管顺序）。
直接对整个大数组排序（
sort）。输出排序后的结果。
为什么可以这样做？
题目已经告诉我们 每个子数组都是有序的，但 合并后的数组不一定有序。
直接 全部存到一个数组里再排序，是最简单的方法（但效率不是最高）。
例子：
3 3 1 5 9 2 2 6 4 3 4 7 8
执行过程
读取输入：
K=3（3 个子数组）。第1个子数组：
[1, 5, 9]（长度3）。第2个子数组：
[2, 6]（长度2）。第3个子数组：
[3, 4, 7, 8]（长度4）。合并到
result：result = [1, 5, 9, 2, 6, 3, 4, 7, 8]（共9个数字）。排序
result：std::sort→[1, 2, 3, 4, 5, 6, 7, 8, 9]。输出：
1 2 3 4 5 6 7 8 9。
【参考答案】
#include <iostream>
#include <algorithm>
using namespace std;
int lists[100][100];//存储所有子数组
int sizes[1000]; //每个子数组的长度（大小）
int result[1000]; //存放最终合并后的数组
int total_size; //合并后数组总长度
void mergeKSortedLists(int K) {
total_size = 0;
// 将所有子序列的元素存入 result
for (int i = 0; i < K; i++) {
for (int j = 0; j < sizes[i]; j++) {
result[total_size++] = lists[i][j]; //把 lists[i][j] 的值存入 result，并让 total_size 指向下一个位置。
}
}
// 直接排序
sort(result, result + total_size);
}
int main() {
int K;
cin >> K;
// 读取输入
for (int i = 0; i < K; i++) {
cin >> sizes[i];
for (int j = 0; j < sizes[i]; j++) {
cin >> lists[i][j];
}
}
//调用函数
mergeKSortedLists(K);
// 输出结果
for (int i = 0; i < total_size; i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}注：很难拿到满分
【思路二】：直接使用优先队列
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int,vector<int>,greater<int> >q;
int n,x,y,i,j;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x;
for(j=1;j<=x;j++)
{
cin>>y;
q.push(y);
}
}
while(!q.empty())
{
cout<<q.top()<<endl;
q.pop();
}
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。