Tối đa hóa mảng đầu tiên bằng cách dùng phần tử từ mảng thứ hai trong C++

Đề bài

Cho hai mảng cùng kích thước n. Tạo mảng mới chứa n phần tử lớn nhất duy nhất từ cả hai mảng, ưu tiên mảng thứ hai (phần tử của arr2 xuất hiện trước), giữ nguyên thứ tự xuất hiện trong mảng gốc.

Ví dụ: arr1={12,15,10}, arr2={16,17,5} → kết quả {16,17,15} (3 phần tử lớn nhất: 17,16,15; 17,16 từ arr2, 15 từ arr1).

Thuật toán

1. Gộp hai mảng vào mảng tạm, sắp xếp giảm dần.
2. Lấy n phần tử lớn nhất duy nhất vào hash set.
3. Duyệt arr2, nếu phần tử có trong set → thêm vào kết quả, xóa khỏi set.
4. Duyệt arr1, nếu phần tử còn trong set → thêm vào kết quả.

Ví dụ minh họa (C++)

#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;
}

void getMaxElements(int* arr1, int* arr2, int n) {
    vector<int> temp(2*n);
    for (int i = 0; i < n; ++i) temp[i] = arr1[i];
    for (int i = 0; i < n; ++i) temp[n+i] = arr2[i];
    sort(temp.begin(), temp.end(), greater<int>());

    unordered_set<int> st;
    for (int i = 0; i < 2*n && st.size() < n; ++i)
        st.insert(temp[i]);

    vector<int> res;
    for (int i = 0; i < n; ++i)
        if (st.count(arr2[i])) { res.push_back(arr2[i]); st.erase(arr2[i]); }
    for (int i = 0; i < n; ++i)
        if (st.count(arr1[i])) { res.push_back(arr1[i]); st.erase(arr1[i]); }

    cout << "Mang toi da: ";
    printArray(res.data(), res.size());
}

int main() {
    int arr1[] = {12, 15, 10};
    int arr2[] = {16, 17, 5};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Mang 1: "; printArray(arr1, n);
    cout << "Mang 2: "; printArray(arr2, n);
    getMaxElements(arr1, arr2, n);
    return 0;
}

Kết quả

Mang 1: 12 15 10
Mang 2: 16 17 5
Mang toi da: 16 17 15