Trong bài viết này, chúng ta sẽ thảo luận cách hợp nhất nhanh hai mảng đã sắp xếp sử dụng hàm std::merge() trong C++ STL.
Trước khi giải quyết, hãy tìm hiểu về std::merge() trong C++ STL.
std::merge() là gì?
std::merge() là hàm tích hợp sẵn trong C++ STL, được định nghĩa trong header <algorithm>. merge() dùng để hợp nhất hai khoảng (ranges) hoặc dãy đã sắp xếp. Hàm này kết hợp hai dãy đã sắp xếp thành một dãy duy nhất cũng đã sắp xếp. Tất cả các phần tử được so sánh bằng toán tử nhỏ hơn (<) nên dãy thứ ba cũng tự động được sắp xếp.
Cách hợp nhất nhanh hai mảng đã sắp xếp bằng std::merge()
Cho hai mảng đã sắp xếp arr1[] và arr2[], nhiệm vụ là hợp nhất chúng lưu vào mảng rỗng arr3[] dùng hàm merge().
Tính kích thước cả hai mảng arr[size_arr] và brr[size_brr], định nghĩa mảng thứ ba có kích thước bằng tổng hai kích thước final[size_arr+size_brr].
Hợp nhất hai mảng vào mảng thứ ba dùng merge(): merge(arr, (arr + size_arr), brr, (brr + size_brr), final);
Ví dụ
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {1, 2, 3};
int size_arr = sizeof(arr)/sizeof(arr[0]);
int brr[] = {4, 5, 6};
int size_brr = sizeof(brr)/sizeof(brr[0]);
int final[size_arr + size_brr];
merge(arr, (arr + size_arr), brr, (brr + size_brr), final);
cout << "Mảng cuối sau khi hợp nhất: ";
for (int i = 0; i < (size_brr + size_arr); i++)
cout << final[i] << " ";
return 0;
}
Kết quả
Mảng cuối sau khi hợp nhất: 1 2 3 4 5 6