資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告