คำชี้แจงปัญหา
กำหนดอาร์เรย์ขนาดเดียวกันสองชุด A[] และ B[] ภารกิจคือการสร้างอาร์เรย์ที่สามที่มีขนาดเท่ากัน อาร์เรย์ผลลัพธ์ควรมีองค์ประกอบสูงสุด n จากทั้งสองอาร์เรย์ ควรเลือกองค์ประกอบของ A[] ก่อน จากนั้นจึงเลือกองค์ประกอบของ B[] ในลำดับเดียวกันกับที่ปรากฏในอาร์เรย์ดั้งเดิม หากมีองค์ประกอบทั่วไป ควรมีเพียงหนึ่งองค์ประกอบใน res[] และควรกำหนดลำดับความสำคัญให้กับ A[]
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น −
arr1[] = {9, 17, 2, 25, 6}
arr2[] = {17, 4, 8, 10, 1} then final array is:
{9, 17, 25, 8, 10} โปรดทราบว่าองค์ประกอบ 17 เป็นเรื่องปกติและให้ความสำคัญกับ arr1
อัลกอริทึม
- สร้างสำเนาของอาร์เรย์ทั้งสองและเรียงลำดับสำเนาจากมากไปหาน้อย
- ใช้แฮชเพื่อเลือก n องค์ประกอบสูงสุดที่ไม่ซ้ำกันของทั้งสองอาร์เรย์ โดยให้ความสำคัญกับ arr1[]
- กำหนดค่าเริ่มต้นอาร์เรย์ผลลัพธ์ให้ว่างเปล่า
- สำรวจผ่าน arr1[] คัดลอกองค์ประกอบเหล่านั้นของ arr1[] ที่มีอยู่ในแฮช สิ่งนี้ทำเพื่อรักษาลำดับขององค์ประกอบเหมือนเดิม
- ทำซ้ำขั้นตอนที่ 4 สำหรับ arr2[] คราวนี้เราพิจารณาเฉพาะองค์ประกอบที่ไม่มีอยู่ใน arr1[]
ตัวอย่าง
เรามาดูตัวอย่างกัน −
#include <bits/stdc++.h>
using namespace std;
void printArray(vector<int> &arr, int n) {
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
void getMaxArray(int *arr1, int *arr2, int n) {
vector<int> temp1(arr1, arr1 + n); vector<int> temp2(arr2, arr2 + n);
sort(temp1.begin(), temp1.end(), greater<int>()); sort(temp2.begin(), temp2.end(), greater<int>());
unordered_map<int, int> m;
int i = 0, j = 0;
while (m.size() < n) {
if (temp1[i] >= temp2[j]) {
m[temp1[i]]++;
++i;
} else {
m[temp2[j]]++;
++j;
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (m.find(arr1[i]) != m.end()) {
result.push_back(arr1[i]);
}
}
for (int i = 0; i < n; ++i) {
if (m.find(arr2[i]) != m.end() && m[arr2[i]] ==1) {
result.push_back(arr2[i]);
}
}
cout << "Final array:\n";
printArray(result, n);
}
int main() {
int arr1[] = {9, 17, 2, 25, 6};
int arr2[] = {17, 4, 8, 10, 1};
int n = sizeof(arr1) / sizeof(arr1[0]);
getMaxArray(arr1, arr2, n);
return 0;
} ผลลัพธ์
Final array: 9 17 25 8 10
