Tạo mảng lớn nhất từ hai mảng cho trước giữ nguyên thứ tự trong C++

Đề bài

Cho hai mảng A[], B[] cùng kích thước n. Tạo mảng kết quả kích thước n chứa n phần tử lớn nhất duy nhất từ cả hai mảng, ưu tiên phần tử của A[] nếu trùng, và giữ nguyên thứ tự xuất hiện trong mảng gốc.

Ví dụ: A={9,17,2,25,6}, B={17,4,8,10,1} → Kết quả {9,17,25,8,10}. (17 trùng, lấy của A).

Thuật toán

1. Sao chép và sắp xếp giảm dần cả hai mảng.
2. Dùng hash set chọn n phần tử lớn nhất duy nhất, ưu tiên A (duyệt A trước).
3. Duyệt A gốc, lấy phần tử có trong hash → thêm vào kết quả.
4. Duyệt B gốc, lấy phần tử có trong hash và chưa lấy từ A → thêm vào kết quả.

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

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

void printArray(vector<int>& arr) {
    for (int x : arr) cout << x << " ";
    cout << endl;
}

void getMaxArray(int* arr1, int* arr2, int n) {
    vector<int> t1(arr1, arr1+n), t2(arr2, arr2+n);
    sort(t1.begin(), t1.end(), greater<int>());
    sort(t2.begin(), t2.end(), greater<int>());

    unordered_map<int, int> mp;
    int i = 0, j = 0;
    while (mp.size() < n) {
        if (t1[i] >= t2[j]) mp[t1[i++]]++;
        else mp[t2[j++]]++;
    }

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

    cout << "Mang ket qua: ";
    printArray(res);
}

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

Kết quả

Mang ket qua: 9 17 25 8 10