Chúng ta được cho một mảng số Arr1[] và mảng khác Arr2[] cùng hoặc khác độ dài. Arr1[] có các phần tử được sắp xếp theo thứ tự tăng dần, ngoại trừ một phần tử không được sắp xếp. Chúng ta phải tìm phần tử từ mảng thứ hai Arr2[] sao cho nó có thể thay thế phần tử đặt sai vị trí của Arr1[] và làm cho nó được sắp xếp. Ngoài ra, phần tử được chọn từ Arr2[] phải là lớn nhất nếu có nhiều lựa chọn.
Ví dụ
Đầu vào
Arr1[] = { 1, 3, 5, 7, 2, 11 }, Arr2[] = { 4, 8, 7, 10, 9 }
Đầu ra
Phần tử tối đa làm Arr1 được sắp xếp: 10
Giải thích − Các số trong Arr2[] có thể làm Arr1[] sắp xếp: 8, 9, 10 vì chúng đều >= 7 và <= 11. Trong đó 10 là lớn nhất.
Arr1[] mới trở thành { 1, 3, 5, 7, 10, 11 } và được sắp xếp.
Đầu vào
Arr1[] = { 12, 5, 22, 17 }, Arr2[] = { 4, 8, 7, 10, 9 }
Đầu ra
Không có phần tử như vậy.
Giải thích − Không có số trong Arr2[] mà >= 12 và <= 22. Arr1[] không thể được sắp xếp.
Phương pháp sử dụng trong chương trình dưới đây
- Mảng arr1[] và arr2[] lưu số. Arr1[] được sắp xếp tăng dần trừ một phần tử.
- Hàm sortMax(int arr1[], int arr2[], int n1, int n2) nhận cả hai mảng và độ dài, cập nhật arr1[] nếu phần tử trong arr2[] được tìm thấy là tối đa và cũng có thể thay thế phần tử sai trong arr[].
- Lưu chỉ số phần tử đặt sai trong arr1[] trong biến wpos, khởi tạo -1.
- maxx dùng để lưu tối đa trong các phần tử arr2[] có thể thay thế phần tử sai của arr1[] và làm cho nó sắp xếp.
- Đầu tiên duyệt arr1[] tìm phần tử sai. Nếu arr[i] < arr[i-1]. Lưu chỉ số trong wpos là i.
- Bây giờ duyệt arr2[] tìm phần tử có thể đặt giữa arr1[wpos-1] và arr[wpos+1]. Cũng nếu phần tử như vậy tồn tại thì so sánh nó với maxx phần tử như vậy.
- Cập nhật maximum.
- Cuối cùng thay thế arr1[wpos] bằng maxx.
- Nếu tìm thấy phần tử như vậy trả về maxx, ngược lại trả về -1.
- Nếu không tìm thấy phần tử thì hiển thị thông báo.
- Ngược lại in arr1[] đã sắp xếp.
Ví dụ mã nguồn
// C++ program to make array sorted
#include <bits/stdc++.h>
using namespace std;
int sortMax(int arr1[], int arr2[], int n1, int n2) { // làm arr1 sắp xếp
int wpos = -1;
int maxx = -1;
int i, j;
for (i = 0; i < n1; i++)
if (arr1[i] < arr1[i - 1])
wpos = i;
for (j = 0; j < n2; j++) {
if (arr2[j] >= arr1[wpos - 1] && arr2[j] <= arr1[wpos + 1])
if (arr2[j] >= maxx)
maxx = arr2[j];
}
if (maxx != -1)
arr1[wpos] = maxx;
return maxx;
}
int main() {
int arr1[] = { 1, 3, 7, 4, 10 };
int arr2[] = { 2, 1, 6, 8, 9 };
int len1 = sizeof(arr1) / sizeof(arr1[0]);
int len2 = sizeof(arr2) / sizeof(arr2[0]);
int res = sortMax(arr1, arr2, len1, len2);
if (res == -1)
cout << "Không thể hoán đổi! Không có phần tử như vậy!";
else {
cout << "Phần tử tối đa trong arr2[] làm arr1[] sắp xếp: " << res;
cout << endl << "Arr1[]: ";
for (int i = 0; i < len1; i++)
cout << arr1[i] << " ";
cout << endl << "Arr2[]: ";
for (int i = 0; i < len2; i++)
cout << arr2[i] << " ";
}
}
Kết quả
Phần tử tối đa trong arr2[] làm arr1[] sắp xếp: 9 Arr1[]: 1 3 7 9 10 Arr2[]: 2 1 6 8 9