Hai mảng, A và B, được cung cấp cho chúng tôi trong hướng dẫn này. Ví dụ:chúng ta cần xuất ra bất kỳ hoán vị nào của A để các chỉ số mà A [I]> B [I] là cực đại, chẳng hạn
Input: A = [12, 22, 41, 13], B = [1, 20, 10, 12] Output: 12, 22, 41, 13 Input: A = [2, 5, 9, 7], B = [1, 12, 4, 54] Output: 2 7 5 9 Multiple answers can be present in that case we are simply going to print any one of the answers.
Trong bài toán này, chúng ta cần tối đa hóa các chỉ số trong đó A [i]> B [i], vì vậy chúng ta sẽ giải quyết vấn đề này một cách tham lam.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, trước tiên chúng ta sẽ sắp xếp cả hai mảng bây giờ; chúng tôi kiểm tra tham lam từng chỉ số của mảng B sao cho A [i] quan trọng hơn nó và sau đó đặt phần tử đó vào một vectơ.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int A[] = { 2, 5, 9, 7 };
int B[] = { 1, 12, 4, 54 };
int n = sizeof(A) / sizeof(int); // size of our arrays
vector<pair<int, int> > A_pair, B_pair;
/***********************We are linking element to its position***********/
for (int i = 0; i < n; i++)
A_pair.push_back({A[i], i});
for (int i = 0; i < n; i++)
B_pair.push_back({B[i], i});
/***********************************************************************/
/*****Sorting our pair vectors********************/
sort(A_pair.begin(), A_pair.end());
sort(B_pair.begin(), B_pair.end());
int i = 0, j = 0, ans[n];
memset(ans, -1, sizeof(ans)); // initializing all the elements with value -1
vector<int> remaining; // this will store our elements which have lesser value than elemnt present in B.
while (i < n && j < n) {
// as our array is sorted then if we find any element in
//current index which has less value than B of current index then
// automatically it will have less value than other elements of B
// that's why we push such indices in remaining otherwise we push element in ans
if (A_pair[i].first > B_pair[j].first) {
ans[B_pair[j].second] = A_pair[i].first;
i++;
j++;
}
else {
remaining.push_back(i);
i++;
}
}
j = 0;
for (int i = 0; i < n; ++i){
// now if any index of answer is unchanged so that means
//we need to fill that position with the remaining elements
if (ans[i] == -1){
ans[i] = A_pair[remaining[j]].first;
j++;
}
}
for (int i = 0; i < n; i++) // printing our answer
cout << ans[i] << " ";
return 0;
} Đầu ra
2 7 5 9
Giải thích về Quy tắc trên
Trong cách tiếp cận này, trước tiên, chúng tôi liên kết tất cả các phần tử với chỉ số của chúng để vẫn có chỉ mục cũ của chúng khi chúng tôi sắp xếp nó. Chúng tôi sắp xếp cả hai vectơ của các cặp bây giờ chúng tôi tham lam tìm kiếm câu trả lời của mình khi chúng tôi di chuyển qua cả hai mảng nếu chúng tôi nhận được một chỉ mục của A_pair có giá trị xuất sắc hơn của B_pair, vì vậy chúng tôi lưu trữ nó trong một mảng của chúng tôi (và trong vị trí của B_pair) khác vì chúng tôi đã sắp xếp cả hai vectơ, vì vậy chúng tôi biết rằng chúng tôi sẽ không thể sử dụng giá trị này của A_pair, vì vậy chúng tôi đẩy chỉ mục phần tử đó trong vectơ còn lại của chúng tôi bây giờ chúng tôi lấp đầy mảng bằng sự trợ giúp của phần còn lại vectơ, và sau đó chúng tôi in câu trả lời.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm Hoán vị của một mảng có các giá trị nhỏ hơn từ một mảng khác. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.