CTDL và giải thuật - Gộp hai dãy thành một dãy
Cho dãy a
gồm n
số nguyên, và dãy b
gồm m
số nguyên, cả hai dãy đều được sắp xếp không giảm.
Hãy gộp hai dãy thành một dãy c
, sao cho dãy c
cũng là dãy không giảm. In dãy c
ra màn hình, sau mỗi phần tử có đúng một dấy cách.
Ví dụ:
- Test mẫu 1:
Input Output 3
1 3 4
4
1 2 3 51 1 2 3 3 4 5
Vớia = [1, 3, 4]
vàb = [1, 2, 4, 5]
thì kết quả mong muốn là:"1 1 2 3 4 4 5 "
.
- Test mẫu 2:
Input Output 3
1 2 3
3
2 3 41 2 2 3 3 4
Vớia = [1, 2, 3]
vàb = [2, 3, 4]
thì kết quả mong muốn là:"1 2 2 3 3 4 "
.
Hướng dẫn bài tập.
Tạo dãy c
rỗng, lần lượt thêm các phần tử vào dãy c
theo thứ tự từ bé đến lớn, do dãy a
và b
đã được sắp xếp, nên ta chỉ cần so sánh 2
giá trị là 2
giá trị nhỏ nhất của mỗi dãy.
Ví dụ với bài trên.
Lúc đầu ta sẽ xét hai số là a[0]
và b[0]
thêm số nhỏ hơn và dãy c
. ta thấy a[0] >= b[0]
nên ta lấy giá trị nhỏ hơn là b[0]
thêm vào dãy c
.
Xét hai số là a[0]
và b[1]
để thêm số nhỏ hơn và dãy c
. Ta thấy a[0] < b[1]
nên ta thêm a[0]
và dãy c
.
Tiếp tục tương tự như vậy đến khi 1
trong 2
dãy hết phần tử để duyệt.
Lúc này 1
trong 2
dãy đã hết phần tử, ta thêm tất cả phần tử của dãy còn lại vào dãy c
.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int a[100001], b[100001], c[100001];
int main(){
int n, m;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
cin >> m;
for (int i = 0; i < m; i++){
cin >> b[i];
}
int size = 0; // lưu số lượng phần tử của dãy c
int i = 0, j = 0;
while (i < n && j < m){
if (a[i] < b[j]){
c[size] = a[i];
size = size + 1;
i = i + 1;
} else {
c[size] = b[j];
size = size + 1;
j = j + 1;
}
}
while (i < n){
c[size] = a[i];
size = size + 1;
i = i + 1;
}
while (j < m){
c[size] = b[j];
size = size + 1;
j = j + 1;
}
for (int i = 0; i < size; i++){
cout << c[i] << " ";
}
return 0;
}