Maximizar elementos usando otra array

Dadas dos arrays con tamaño n, maximice la primera array usando los elementos de la segunda array de modo que la nueva array formada contenga n elementos más grandes pero únicos de ambas arrays dando prioridad a la segunda array (Todos los elementos de la segunda array aparecen antes de la primera array ). El orden de aparición de los elementos se mantiene igual en la salida que en la entrada.
Ejemplos:

Entrada: arr1[] = {2, 4, 3} 
arr2[] = {5, 6, 1} 
Salida: 5 6 4 
Como 5, 6 y 4 son los elementos máximos de dos arrays que le dan mayor prioridad a la segunda array. El orden de los elementos es el mismo en la salida que en la entrada.
Entrada: arr1[] = {7, 4, 8, 0, 1} 
arr2[] = {9, 7, 2, 3, 6} 
Salida: 9 7 6 4 8

Enfoque: creamos una array auxiliar de tamaño 2*n y almacenamos los elementos de la segunda array en una array auxiliar, y luego almacenaremos los elementos de la primera array en ella. Después de eso, ordenaremos la array auxiliar en orden decreciente. Para mantener el orden de los elementos de acuerdo con las arrays de entrada, usaremos la tabla hash. Almacenaremos los primeros n elementos únicos más grandes de la array auxiliar en la tabla hash. Ahora recorremos la segunda array y almacenamos los elementos de la segunda array en una array auxiliar que están presentes en la tabla hash. De manera similar, recorreremos la primera array y almacenaremos los elementos que están presentes en la tabla hash. De esta manera, obtenemos n elementos únicos y más grandes de ambas arrays en una array auxiliar mientras mantenemos el mismo orden de aparición de los elementos.
A continuación se muestra la implementación del enfoque anterior:

// C++ program to print the maximum elements
// giving second array higher priority
#include <bits/stdc++.h>
using namespace std;
 
// Compare function used to sort array
// in decreasing order
bool compare(int a, int b)
{
    return a > b;
}
 
// Function to maximize array elements
void maximizeArray(int arr1[], int arr2[],
                                   int n)
{
    // auxiliary array arr3 to store
    // elements of 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];
 
    // hash table to store n largest
    // unique elements
    unordered_set<int> hash;
 
    // sorting arr3 in decreasing order
    sort(arr3, arr3 + 2 * n, compare);
 
    // finding n largest unique elements
    // from arr3 and storing in hash
    int i = 0;
    while (hash.size() != n) {
 
        // if arr3 element not present in hash,
        // then store this element in hash
        if (hash.find(arr3[i]) == hash.end())
            hash.insert(arr3[i]);
         
        i++;
    }
 
    // store that elements of arr2 in arr3
    // that are present in hash
    k = 0;
    for (int i = 0; i < n; i++) {
 
        // if arr2 element is present in hash,
        // store it in arr3
        if (hash.find(arr2[i]) != hash.end()) {
            arr3[k++] = arr2[i];
            hash.erase(arr2[i]);
        }
    }
 
    // store that elements of arr1 in arr3
    // that are present in hash
    for (int i = 0; i < n; i++) {
 
        // if arr1 element is present in hash,
        // store it in arr3
        if (hash.find(arr1[i]) != hash.end()) {
            arr3[k++] = arr1[i];
            hash.erase(arr1[i]);
        }
    }
 
    // copying 1st n elements of arr3 to arr1
    for (int i = 0; i < n; i++)
        arr1[i] = arr3[i];   
}
 
// Function to print array elements
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";   
    cout << endl;
}
 
// Driver Code
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);
}

// Java program to print the maximum elements
// giving second array higher priority
import java.util.*;
 
class GFG
{
 
// Function to maximize array elements
static void maximizeArray(int[] arr1,int[] arr2)
{
    // auxiliary array arr3 to store
    // elements of arr1 & arr2
    int arr3[] = new int[10];
    for(int i = 0; i < arr3.length; i++)
    {
        //arr2 has high priority
        arr3[i] = 0;
    }
     
    // Arraylist to store n largest
    // unique elements
    ArrayList<Integer> al = new ArrayList<Integer>();
     
    for(int i = 0; i < arr2.length; i++)
    {
        if(arr3[arr2[i]] == 0)
        {
            // to avoid repetition of digits of arr2 in arr3
            arr3[arr2[i]] = 2;
             
            // simultaneously setting arraylist to
            // preserve order of arr2 and arr3
            al.add(arr2[i]);
        }
    }
     
    for(int i = 0; i < arr1.length; i++)
    {
        if(arr3[arr1[i]] == 0)
        {
            // if digit is already present in arr2
            // then priority is arr2
            arr3[arr1[i]] = 1;
             
            // simultaneously setting arraylist to
            // preserve order of arr1
            al.add(arr1[i]);
        }
    }
 
    // to get only highest n elements(arr2+arr1)
    // and remove others from arraylist
    int count = 0;
    for(int j = 9; j >= 0; j--)
    {
        if(count < arr1.length &
          (arr3[j] == 2 || arr3[j] == 1))
        {
            // to not allow those elements
            // which are absent in both arrays
            count++;
        }
        else
        {
            al.remove(Integer.valueOf(j));
        }
    }
 
    int i = 0;
    for(int x:al)
    {
        arr1[i++] = x;
    }
}
 
// Function to print array elements
static void printArray(int[] arr)
{
    for(int x:arr)
    {
        System.out.print(x + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int arr1[] = {7, 4, 8, 0, 1};
    int arr2[] = {9, 7, 2, 3, 6};
    maximizeArray(arr1,arr2);
    printArray(arr1);
}
}
 
// This code is contributed by KhwajaBilkhis

# Python3 program to print the maximum elements
# giving second array higher priority
 
# Function to maximize array elements
def maximizeArray(arr1, arr2, n):
     
    # Auxiliary array arr3 to store
    # elements of arr1 & arr2
    arr3 = [0] * (2 * n)
    k = 0
     
    for i in range(n):
        arr3[k] = arr1[i]
        k += 1
         
    for i in range(n):
        arr3[k] = arr2[i]
        k += 1
 
    # Hash table to store n largest
    # unique elements
    hash = {}
 
    # Sorting arr3 in decreasing order
    arr3 = sorted(arr3)
    arr3 = arr3[::-1]
 
    # Finding n largest unique elements
    # from arr3 and storing in hash
    i = 0
    while (len(hash) != n):
 
        # If arr3 element not present in hash,
        # then store this element in hash
        if (arr3[i] not in hash):
            hash[arr3[i]] = 1
 
        i += 1
 
    # Store that elements of arr2 in arr3
    # that are present in hash
    k = 0
    for i in range(n):
 
        # If arr2 element is present in
        # hash, store it in arr3
        if (arr2[i] in hash):
            arr3[k] = arr2[i]
            k += 1
             
            del hash[arr2[i]]
 
    # Store that elements of arr1 in arr3
    # that are present in hash
    for i in range(n):
 
        # If arr1 element is present
        # in hash, store it in arr3
        if (arr1[i] in hash):
            arr3[k] = arr1[i]
            k += 1
             
            del hash[arr1[i]]
 
    # Copying 1st n elements of
    # arr3 to arr1
    for i in range(n):
        arr1[i] = arr3[i]
 
# Function to print array elements
def printArray(arr, n):
     
    for i in arr:
        print(i, end = " ")
         
    print()
 
# Driver Code
if __name__ == '__main__':
     
    array1 = [ 7, 4, 8, 0, 1 ]
    array2 = [ 9, 7, 2, 3, 6 ]
    size = len(array1)
     
    maximizeArray(array1, array2, size)
    printArray(array1, size)
     
# This code is contributed by mohit kumar 29

// C# program to print the maximum elements
// giving second array higher priority
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to maximize array elements
static void maximizeArray(int[] arr1, int[] arr2)
{
    // auxiliary array arr3 to store
    // elements of arr1 & arr2
    int []arr3 = new int[10];
    for(int i = 0; i < arr3.Length; i++)
    {
        //arr2 has high priority
        arr3[i] = 0;
    }
     
    // Arraylist to store n largest
    // unique elements
    List<int> al = new List<int>();
     
    for(int i = 0; i < arr2.Length; i++)
    {
        if(arr3[arr2[i]] == 0)
        {
            // to avoid repetition of digits of arr2 in arr3
            arr3[arr2[i]] = 2;
             
            // simultaneously setting arraylist to
            // preserve order of arr2 and arr3
            al.Add(arr2[i]);
        }
    }
     
    for(int i = 0; i < arr1.Length; i++)
    {
        if(arr3[arr1[i]] == 0)
        {
            // if digit is already present in arr2
            // then priority is arr2
            arr3[arr1[i]] = 1;
             
            // simultaneously setting arraylist to
            // preserve order of arr1
            al.Add(arr1[i]);
        }
    }
 
    // to get only highest n elements(arr2+arr1)
    // and remove others from arraylist
    int count = 0;
    for(int j = 9; j >= 0; j--)
    {
        if(count < arr1.Length &
        (arr3[j] == 2 || arr3[j] == 1))
        {
            // to not allow those elements
            // which are absent in both arrays
            count++;
        }
        else
        {
            al.Remove(j);
        }
    }
 
    int c = 0;
    foreach(int x in al)
    {
        arr1[c++] = x;
    }
}
 
// Function to print array elements
static void printArray(int[] arr)
{
    foreach(int x in arr)
    {
        Console.Write(x + " ");
    }
}
 
// Driver Code
public static void Main(String []args)
{
    int []arr1 = {7, 4, 8, 0, 1};
    int []arr2 = {9, 7, 2, 3, 6};
    maximizeArray(arr1, arr2);
    printArray(arr1);
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript program to print the maximum elements
// giving second array higher priority
 
// Function to maximize array elements
function maximizeArray(arr1,arr2)
{
 
    // auxiliary array arr3 to store
    // elements of arr1 & arr2
    let arr3 = new Array(10);
    for(let i = 0; i < arr3.length; i++)
    {
        // arr2 has high priority
        arr3[i] = 0;
    }
       
    // Arraylist to store n largest
    // unique elements
    let al = [];
       
    for(let i = 0; i < arr2.length; i++)
    {
        if(arr3[arr2[i]] == 0)
        {
         
            // to avoid repetition of digits of arr2 in arr3
            arr3[arr2[i]] = 2;
               
            // simultaneously setting arraylist to
            // preserve order of arr2 and arr3
            al.push(arr2[i]);
        }
    }
     
    for(let i = 0; i < arr1.length; i++)
    {
        if(arr3[arr1[i]] == 0)
        {
         
            // if digit is already present in arr2
            // then priority is arr2
            arr3[arr1[i]] = 1;
               
            // simultaneously setting arraylist to
            // preserve order of arr1
            al.push(arr1[i]);
        }
    }
   
    // to get only highest n elements(arr2+arr1)
    // and remove others from arraylist
    let count = 0;
    for(let j = 9; j >= 0; j--)
    {
        if(count < arr1.length &
          (arr3[j] == 2 || arr3[j] == 1))
        {
         
            // to not allow those elements
            // which are absent in both arrays
            count++;
        }
        else
        {   
             
            if(al.indexOf(j)>0)
                al.splice(al.indexOf(j),1);
                 
        }
    }
   
    let i = 0;
    for(let x = 0; x < al.length; x++)
    {
        arr1[i++] = al[x];
    }
    
}
 
// Function to print array elements
function printArray(arr)
{
    for(let x=0; x<arr.length;x++)
    {
        document.write(arr[x] + " ");
    }
}
 
// Driver Code
let arr1=[7, 4, 8, 0, 1];
let arr2=[9, 7, 2, 3, 6];
maximizeArray(arr1,arr2);
printArray(arr1);
     
// This code is contributed by patel2127
</script>

9 7 6 4 8

Complejidad temporal: O(n * log n).

Espacio Auxiliar: O(n)