k路歸併 O(nlogk)
題目
假定有k個有序陣列,每個陣列中含有n個元素,您的任務是將它們合併為單獨的一個有序陣列,該陣列共有kn個元素。設計和實現 一個有效的分治演算法解決k-路合併操作問題,並分析時間複雜度。
演算法思想
採用分治法歸併排序,歸併兩個有序陣列時間複雜度為O(n),將K個有序陣列分治歸併時間複雜度為O(logk),演算法整體時間複雜度為O(nlogk),程式裡用到了vector向量容器。
#include <iostream> #include <vector> using namespace std; vector<int> mergeTowArrays(vector<int>A,vector<int>B) { vector<int>temp; temp.resize(A.size() + B.size()); int index = 0, j = 0, i = 0; while (i < A.size() && j < B.size()) { if (A[i] < B[j]) temp[index++] = A[i++]; else temp[index++] = B[j++]; } while (i < A.size()) temp[index++] = A[i++]; while (j < B.size()) temp[index++] = B[j++]; return temp; } vector<int> kMergeSort(vector<vector<int>>A, int start, int end) { if (start >= end) return A[start]; int mid = start + (end - start) / 2; vector<int>Left = kMergeSort(A, start, mid); vector<int>Right = kMergeSort(A, mid + 1, end); return mergeTowArrays(Left, Right); } vector<int> mergeSortArrays(vector <vector<int>>A) { vector<int>temp; if (A.empty() || A.size() == 0 || A[0].size() == 0) return temp; temp = kMergeSort(A, 0, A.size() - 1); return temp; } int main(void) { int k,n; cin >> k >> n; vector<vector<int>>A(k); for (int i = 0; i < k; i++) { A[i].resize(n); } for (int i = 0; i < A.size(); i++) { for (int j = 0; j < A[0].size(); j++) cin >> A[i][j]; } vector<int>result; result = mergeSortArrays(A); for (int i = 0; i < result.size(); i++) { cout << result[i] << " "; } cout << endl; system("pause"); return 0; }