สองอาร์เรย์ A และ B มอบให้เราในบทช่วยสอนนี้ ตัวอย่างเช่น เราจำเป็นต้องส่งออกการเรียงสับเปลี่ยนของ A เพื่อให้ดัชนีที่ A[ I ]> B[ I ] ขยายใหญ่สุด ตัวอย่างเช่น
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.
ในปัญหานี้ เราจำเป็นต้องเพิ่มดัชนีให้มากที่สุดโดยที่ A[ i ]> B[ i ] ดังนั้นเราจะแก้ปัญหานี้อย่างตะกละตะกลาม
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ ก่อนอื่นเราจะเรียงลำดับอาร์เรย์ทั้งสองตอนนี้ เราตรวจสอบแต่ละดัชนีของอาร์เรย์ B อย่างตะกละตะกลามเพื่อให้ A[ i ] มีความสำคัญมากกว่านั้น แล้ววางองค์ประกอบนั้นในเวกเตอร์
ตัวอย่าง
#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;
} ผลลัพธ์
2 7 5 9
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ ก่อนอื่นเราจะเชื่อมโยงองค์ประกอบทั้งหมดกับดัชนีเพื่อให้มีดัชนีเดิมอยู่ในนั้นเมื่อเราจัดเรียง เราจัดเรียงเวกเตอร์ของคู่ทั้งสองตอนนี้เราค้นหาคำตอบของเราอย่างตะกละตะกลามเมื่อเราเคลื่อนผ่านทั้งสองอาร์เรย์หากเราได้รับดัชนี A_pair ซึ่งมีค่ามากกว่า B_pair ดังนั้นเราจึงเก็บไว้ในอาร์เรย์ของเรา (และใน ตำแหน่งของ B_pair) อย่างอื่นเมื่อเราจัดเรียงเวกเตอร์ทั้งสองแล้ว ดังนั้นเรารู้ว่าเราจะไม่สามารถใช้ค่าของ A_pair นี้ได้ ดังนั้นเราจึงผลักดัชนีองค์ประกอบนั้นในเวกเตอร์ที่เหลือของเรา ตอนนี้เราเติมอาร์เรย์ด้วยความช่วยเหลือที่เหลือ เวกเตอร์ แล้วเราก็พิมพ์คำตอบออกมา
บทสรุป
ในบทช่วยสอนนี้ เราแก้ปัญหาเพื่อค้นหาการเรียงสับเปลี่ยนของอาร์เรย์ที่มีค่าน้อยกว่าจากอาร์เรย์อื่น นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางทั้งหมดที่เราแก้ไข เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
