เพิ่มค่าองค์ประกอบอาร์เรย์โดยใช้อาร์เรย์อีกอันใน C++

โจทย์

ได้รับอาร์เรย์สองอันขนาด n เพิ่มค่าอาร์เรย์แรกโดยใช้องค์ประกอบจากอาร์เรย์ที่สอง อาร์เรย์ใหม่ต้องมี N องค์ประกอบที่มากที่สุดและไม่ซ้ำจากทั้งสองอาร์เรย์ ให้ความสำคัญกับอาร์เรย์ที่สอง คือ องค์ประกอบของอาร์เรย์ที่สองต้องมาก่อนอาร์เรย์แรก ลำดับการปรากฏต้องเหมือนเดิม

ถ้า arr1[] = {12, 15, 10} และ arr2[] = {16, 17, 5} แล้ว {16, 17, 15} คือองค์ประกอบสูงสุดจากทั้งสองอาร์เรย์โดยรักษาลำดับ

อัลกอริทึม

1. สร้าง Temporary Array ขนาด 2*n
2. เก็บองค์ประกอบ arr1 และ arr2 ใน Temporary Array และจัดเรียง Descending
3. ใช้ Hash Table เพื่อรักษาลำดับตามอินพุต
4. เก็บ N องค์ประกอบมากที่สุดไม่ซ้ำของ Temporary Array ใน Hash
5. ท่อง arr2 เก็บองค์ประกอบที่อยู่ใน Hash ลง Temporary Array
6. ท่อง arr1 ทำเหมือนกัน สำหรับองค์ประกอบที่ยังอยู่ใน Hash
7. ได้ N องค์ประกอบมากที่สุดไม่ซ้ำจากทั้งสองอาร์เรย์ใน Temporary Array

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

void printArray(int* arr, int n) {
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

bool compare(int a, int b) {
    return a > b;
}

void getMaxElements(int* arr1, int* arr2, int n) {
    int temp[2 * n];
    int k = 0;
    for (int i = 0; i < n; ++i) {
        temp[k] = arr1[i];
        ++k;
    }
    for (int i = 0; i < n; ++i) {
        temp[k] = arr2[i];
        ++k;
    }
    sort(temp, temp + 2 * n, compare);
    unordered_set<int> hash;
    int i = 0;
    while (hash.size() != n) {
        if (hash.find(temp[i]) == hash.end()) {
            hash.insert(temp[i]);
        }
        ++i;
    }
    k = 0;
    for (int i = 0; i < n; ++i) {
        if (hash.find(arr2[i]) != hash.end()) {
            temp[k++] = arr2[i];
            hash.erase(arr2[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (hash.find(arr1[i]) != hash.end()) {
            temp[k++] = arr1[i];
            hash.erase(arr1[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        arr1[i] = temp[i];
    }
}

int main() {
    int arr1[] = {12, 15, 10};
    int arr2[] = {16, 17, 5};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    cout << "First array:\n";
    printArray(arr1, n);
    cout << "Second array:\n";
    printArray(arr2, n);
    getMaxElements(arr1, arr2, n);
    cout << "Maximum array:\n";
    printArray(arr1, n);
    return 0;
}

ผลลัพธ์

First array: 12 15 10
Second array: 16 17 5
Maximum array: 16 17 15