ในบทช่วยสอนนี้ ให้อาร์เรย์สองตัว 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 หลายคำตอบอาจเป็นไปได้ ในกรณีนั้นเราจะพิมพ์คำตอบใดคำตอบหนึ่ง
ในปัญหานี้ เราต้องเพิ่มดัชนีที่ A[i] > B[i] ให้มากที่สุด ดังนั้นเราจะแก้ปัญหานี้แบบ Greedy (貪婪算法)
วิธีการแก้ปัญหา
ในวิธีนี้ เราจะจัดเรียงอาร์เรย์ทั้งสองก่อน ตอนนี้เราตรวจสอบแบบ Greedy สำหรับแต่ละดัชนีของอาร์เรย์ B ว่า A[i] มากกว่ามันหรือไม่ แล้ววางสมาชิกนั้นใน Vector
ตัวอย่าง
#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);
vector<pair<int, int> > A_pair, B_pair;
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});
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));
vector<int> remaining;
while (i < n && j < n) {
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){
if (ans[i] == -1){
ans[i] = A_pair[remaining[j]].first;
j++;
}
}
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
return 0;
}
ผลลัพธ์
2 7 5 9
คำอธิบายโค้ด
ในวิธีนี้ เราเชื่อมโยงสมาชิกทั้งหมดกับดัชนีของพวกเขาก่อน เพื่อให้ยังคงมีดัชนีเดิมเมื่อเราจัดเรียง เราจัดเรียง Vector ของ Pair ทั้งสอง ตอนนี้เราค้นหาคำตอบแบบ Greedy ขณะเคลื่อนผ่านอาร์เรย์ทั้งสอง หากเราพบดัชนีของ A_pair ที่มีค่ามากกว่า B_pair เราจะเก็บไว้ในอาร์เรย์ ans (ที่ตำแหน่งของ B_pair) มิฉะนั้น เนื่องจากเราจัดเรียง Vector ทั้งสองแล้ว เรารู้ว่าเราจะไม่สามารถใช้ค่านี้ของ A_pair ได้ จึงแทรกดัชนีของสมาชิกนั้นลงใน Vector remaining ตอนนี้เราเติมอาร์เรย์ด้วยความช่วยเหลือของ Vector remaining แล้วพิมพ์คำตอบ
สรุป
ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Permutation of an array with smaller values from another array เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์
