C++程序使用另一个数组来最大化元素

给定两个大小为n的数组，通过使用第二个数组中的元素来最大化第一个数组，使得所形成的新数组包含两个数组中n个最大但唯一的元素，第二个数组具有优先权（所有第二个数组的元素出现在第一个数组之前）。输出中元素的出现顺序与输入相同。

示例：

输入：arr1[] = {2, 4, 3}

arr2[] = {5, 6, 1}

输出：5 6 4

因为5、6和4是两个数组中最大的元素，第二个数组优先权更高。元素出现的顺序与输入相同。
输入：arr1[] = {7, 4, 8, 0, 1}

arr2[] = {9, 7, 2, 3, 6}

输出：9 7 6 4 8

方法： 我们创建一个大小为2n的辅助数组，并将第二个数组中的元素存储在其中，然后在其后存储第一个数组中的元素。之后，我们将按递减顺序对辅助数组进行排序。为了根据输入数组保持元素的顺序，我们将使用哈希表。我们将在哈希表中存储前n个最大的唯一元素。现在我们遍历第二个数组，并将在哈希表中存在的第二个数组的元素存储在辅助数组中。类似地，我们将遍历第一个数组并存储在哈希表中存在的元素。通过这种方式，我们从两个数组中获得n个唯一且最大的元素，同时保持元素出现顺序相同。

下面是上述方法的实现：

// C++程序打印最大元素的数组
// 以第二个数组优先
#include <bits/stdc++.h>
using namespace std;
 
//比较函数用于按降序排序数组
bool compare(int a, int b)
{
    return a > b;
}
 
//最大化数组元素的函数
void maximizeArray(int arr1[], int arr2[],
                                   int n)
{
    //辅助数组arr3以存储
    // arr1和arr2的元素
    int arr3[2*n], k = 0;
    for (int i = 0; i < n; i++)
        arr3[k++] = arr1[i];
    for (int i = 0; i < n; i++)
        arr3[k++] = arr2[i];
 
    //哈希表存储n个最大的
    //唯一元素
    unordered_set<int> hash;
 
    //将arr3按降序排序
    sort(arr3, arr3 + 2 * n, compare);
 
    //从arr3中找到n个最大的唯一元素
    //将它们存储在哈希表中
    int i = 0;
    while (hash.size() != n) {
 
        // 如果arr3的元素不在哈希表中，
        // 那么将这个元素存储在哈希表中
        if (hash.find(arr3[i]) == hash.end())
            hash.insert(arr3[i]);
         
        i++;
    }
 
    //将arr2中的元素存储在arr3中
    //那些在哈希表中的元素
    k = 0;
    for (int i = 0; i < n; i++) {
 
        // 如果arr2的元素在哈希表中存在，
        // 将它存储在arr3中
        if (hash.find(arr2[i]) != hash.end()) {
            arr3[k++] = arr2[i];
            hash.erase(arr2[i]);
        }
    }
 
    //将arr1中的元素存储在arr3中
    //那些在哈希表中的元素
    for (int i = 0; i < n; i++) {
 
        // 如果arr1的元素在哈希表中存在，
        // 将它存储在arr3中
        if (hash.find(arr1[i]) != hash.end()) {
            arr3[k++] = arr1[i];
            hash.erase(arr1[i]);
        }
    }
 
    //将arr3的前n个元素复制到arr1
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];   
}
 
//用于打印数组元素的函数
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";   
    cout << endl;
}
 
//驱动程序
int main()
{
    int array1[] = { 7, 4, 8, 0, 1 };
    int array2[] = { 9, 7, 2, 3, 6 };
    int size = sizeof(array1) / sizeof(array1[0]);
    maximizeArray(array1, array2, size);
    printArray(array1, size);
}