数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中合并 k 个不同大小的已排序数组
假设我们有 k 个不同的已排序数组。我们需要合并这些数组并显示排序后的结果。
因此，如果输入类似于 k = 3 且数组为 {2, 4},{3, 5, 7},{1, 10, 11, 12}，则输出将为 1 2 3 4 5 7 10 11 12
为了解决这个问题，我们将遵循以下步骤：
- 定义一种类型的对，其第一个元素是整数，第二个元素是另一个整数对，将其命名为 ppi。
- 定义一个数组 op
- 定义一个优先级队列 q
- 对于初始化 i := 0，当 i < arr 的大小，更新（i 增加 1），执行：
- 将 (arr[i, 0], {i, 0} ) 插入 q
- 当 q 不为空时，执行：
- current_element := q 的顶层元素
- 从 q 中删除元素
- i := current_element 中的第二个元素
- j := current_element 中的第三个元素
- 将 current_element 的第一个元素插入 op 的末尾
- 如果 j + 1 < arr[i] 的大小，则：
- 将 (arr[i, j+1], {i, j+1} ) 插入 q
- 返回 op
示例
让我们看看以下实现以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
#define ppi pair<int,pair<int,int>>
vector<int> merge(vector<vector<int> > arr){
vector<int> op;
priority_queue<ppi, vector<ppi>, greater<ppi> > queue;
for (int i = 0; i < arr.size(); i++)
queue.push({ arr[i][0], { i, 0 } });
while (queue.empty() == false) {
ppi current_element = queue.top();
queue.pop();
int i = current_element.second.first;
int j = current_element.second.second;
op.push_back(current_element.first);
if (j + 1 < arr[i].size())
queue.push({ arr[i][j + 1], { i, j + 1 } });
}
return op;
}
int main(){
vector<vector<int> > arr{ { 2,4}, { 3,5,7 }, { 1, 10, 11, 12 } };
vector<int> output = merge(arr);
for(int i = 0; i<output.size(); i++)
cout << output[i] << " ";
}输入
{{ 2,4}, { 3,5,7 }, { 1, 10, 11, 12 }}输出
1 2 3 4 5 7 10 11 12
更新于: 2020-08-27
520 次浏览
广告