Array máxima de dos arrays dadas manteniendo el mismo orden

Dados dos arreglos del mismo tamaño A[] y B[] (ambos arreglos contienen elementos distintos individualmente pero pueden tener algunos elementos comunes), la tarea es formar un tercer arreglo (o resultado) del mismo tamaño. La array resultante debe tener un máximo de n elementos de ambas arrays. Primero debería haber elegido los elementos de A[], luego los elementos de B[] en el mismo orden en que aparecen en las arrays originales. Si hay elementos comunes, entonces solo un elemento debe estar presente en res[] y se debe dar prioridad a A[].

Ejemplos:  

Input :  A[] =  [ 9 7 2 3 6 ]
         B[] =  [ 7 4 8 0 1 ]
Output : res[] = [9 7 6 4 8]
res[] has maximum n elements of both A[] 
and B[] such that elements of A[] appear
first (in same order), then elements of B[].
Also 7 is common and priority is given to
A's 7.

Input :  A[] = [ 6 7 5 3 ]
         B[] = [ 5 6 2 9 ] 
Output : res[] = [ 6 7 5 9 ]

1. Cree copias de ambas arrays y ordene las copias en orden decreciente. 
2. Use un hash para seleccionar n elementos máximos únicos de ambas arrays, dando prioridad a A[]. 
3. Inicializa la array de resultados como vacía. 
4. Recorra A[], copie los elementos de A[] que están presentes en el hash. Esto se hace para mantener el mismo orden de los elementos. 
5. Repita el paso 4 para B[]. Esta vez solo consideramos aquellos elementos que no están presentes en A[] (No aparecen dos veces en el hash).

A continuación se muestra la implementación de la idea anterior. 

// Make a set of maximum elements from two
// arrays A[] and B[]
#include <bits/stdc++.h>
using namespace std;
 
void maximizeTheFirstArray(int A[], int B[],
                                    int n)
{
    // Create copies of A[] and B[] and sort
    // the copies in descending order.
    vector<int> temp1(A, A+n);
    vector<int> temp2(B, B+n);
    sort(temp1.begin(), temp1.end(), greater<int>());
    sort(temp2.begin(), temp2.end(), greater<int>());
 
    // Put maximum n distinct elements of
    // both sorted arrays in a map.
    unordered_map<int, int> m;
    int i = 0, j = 0;
    while (m.size() < n)
    {
         if (temp1[i] >= temp2[j])
         {
            m[temp1[i]]++;
            i++;
         }
         else
         {
            m[temp2[j]]++;
            j++;
         }
    }
 
    // Copy elements of A[] to that
    // are present in hash m.
    vector<int> res;
    for (int i = 0; i < n; i++)
        if (m.find(A[i]) != m.end())
           res.push_back(A[i]);
 
    // Copy elements of B[] to that
    // are present in hash m. This time
    // we also check if the element did
    // not appear twice.
    for (int i = 0; i < n; i++)
        if (m.find(B[i]) != m.end() &&
            m[B[i]] == 1)
           res.push_back(B[i]);
 
    // print result
    for (int i = 0; i < n; i++)
        cout << res[i] << " ";
}
 
// driver program
int main()
{
    int A[] = { 9, 7, 2, 3, 6 };
    int B[] = { 7, 4, 8, 0, 1 };
    int n = sizeof(A) / sizeof(A[0]);
    maximizeTheFirstArray(A, B, n);
    return 0;
}

// Make a set of maximum elements from two
// arrays A[] and B[]
import java.io.*;
import java.util.*;
class GFG
{
     
    static void maximizeTheFirstArray(int[] A, int[] B,int n)
    {
       
        // Create copies of A[] and B[] and sort
        // the copies in descending order.
        ArrayList<Integer> temp1 = new ArrayList<Integer>();
        ArrayList<Integer> temp2 = new ArrayList<Integer>();
        for(int i : A)
        {
            temp1.add(i);
        }
        for(int i:B)
        {
            temp2.add(i);
        }
        Collections.sort(temp1, Collections.reverseOrder());
        Collections.sort(temp2, Collections.reverseOrder());
         
        // Put maximum n distinct elements of
        // both sorted arrays in a map.
        Map<Integer,Integer> m = new HashMap<>();
        int i = 0, j = 0;
        while (m.size() < n)
        {
             if (temp1.get(i) >= temp2.get(j))
             {
                if(m.containsKey(temp1.get(i)))
                {
                    m.put(temp1.get(i), m.get(temp1.get(i)) + 1);
                }
                else
                {
                    m.put(temp1.get(i), 1);
                }
                i++;
             }
             else
             {
                if(m.containsKey(temp2.get(j)))
                {
                    m.put(temp2.get(j), m.get(temp2.get(j)) + 1);
                }
                else
                {
                    m.put(temp2.get(j), 1);
                }
                j++;
             }
        }
         
        // Copy elements of A[] to that
        // are present in hash m.
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (i = 0; i < n; i++)
            if (m.containsKey(A[i]))
               res.add(A[i]);
      
        // Copy elements of B[] to that
        // are present in hash m. This time
        // we also check if the element did
        // not appear twice.
        for (i = 0; i < n; i++)
            if (m.containsKey(B[i]) && m.get(B[i]) == 1)
               res.add(B[i]);
      
        // print result
        for (i = 0; i < n; i++)
            System.out.print(res.get(i)+" ");
    }
      
    // Driver program   
    public static void main (String[] args)
    {
        int A[] = { 9, 7, 2, 3, 6 };
        int B[] = { 7, 4, 8, 0, 1 };
        int n = A.length;
        maximizeTheFirstArray(A, B, n);
    }
}
 
// This code is contributed by rag2127

# Python3 program to implement the
# above approach
# Make a set of maximum elements
# from two arrays A[] and B[]
from collections import defaultdict
 
def maximizeTheFirstArray(A, B, n):
 
    # Create copies of A[] and B[]
    # and sort the copies in
    # descending order.
    temp1 = A.copy()
    temp2 = B.copy()
    temp1.sort(reverse = True)
    temp2.sort(reverse = True)
 
    # Put maximum n distinct
    # elements of both sorted
    # arrays in a map.
    m = defaultdict(int)
    i = 0
    j = 0;
     
    while (len(m) < n):
         if (temp1[i] >= temp2[j]):
            m[temp1[i]] += 1
            i += 1       
         else:
            m[temp2[j]] += 1
            j += 1
 
    # Copy elements of A[] to that
    # are present in hash m.
    res = []
     
    for i in range (n):
        if (A[i] in m):
           res.append(A[i])
 
    # Copy elements of B[] to that
    # are present in hash m. This time
    # we also check if the element did
    # not appear twice.
    for i in range (n):
        if (B[i] in m and
            m[B[i]] == 1):
           res.append(B[i])
 
    # Print result
    for i in range (n):
        print (res[i], end = " ")
 
# Driver code
if __name__ == "__main__":
   
    A = [9, 7, 2, 3, 6]
    B = [7, 4, 8, 0, 1]
    n = len(A)
    maximizeTheFirstArray(A, B, n);
   
# This code is contributed by Chitranayal

// Make a set of maximum elements from two
// arrays A[] and B[]
using System;
using System.Collections.Generic;
 
class GFG{
 
static void maximizeTheFirstArray(int[] A, int[] B,
                                  int n)
{
     
    // Create copies of A[] and B[] and sort
    // the copies in descending order.
    List<int> temp1 = new List<int>();
    List<int> temp2 = new List<int>();
     
    foreach(int i in A)
    {
        temp1.Add(i);
    }
     
    foreach(int i in B)
    {
        temp2.Add(i);
    }
     
    temp1.Sort();
    temp1.Reverse();
    temp2.Sort();
    temp2.Reverse();
      
    // Put maximum n distinct elements of
    // both sorted arrays in a map.
    Dictionary<int,
               int> m = new Dictionary<int,
                                       int>();
    int I = 0, j = 0;
    while (m.Count < n)
    {
        if (temp1[I] >= temp2[j])
        {
            if (m.ContainsKey(temp1[I]))
            {
                m[temp1[I]]++;
            }
            else
            {
                m.Add(temp1[I], 1);
            }
            I++;
        }
        else
        {
            if (m.ContainsKey(temp2[j]))
            {
                m[temp2[j]]++;
            }
            else
            {
                m.Add(temp2[j], 1);
            }
            j++;
        }
    }
 
    // Copy elements of A[] to that
    // are present in hash m.
    List<int> res = new List<int>();
    for(int i = 0; i < n; i++)
        if (m.ContainsKey(A[i]))
            res.Add(A[i]);
   
    // Copy elements of B[] to that
    // are present in hash m. This time
    // we also check if the element did
    // not appear twice.
    for(int i = 0; i < n; i++)
        if (m.ContainsKey(B[i]) && m[B[i]] == 1)
            res.Add(B[i]);
   
    // print result
    for(int i = 0; i < n; i++)
        Console.Write(res[i] + " ");
}
   
// Driver Code
static public void Main()
{
    int[] A = { 9, 7, 2, 3, 6 };
    int[] B = { 7, 4, 8, 0, 1 };
    int n = A.Length;
     
    maximizeTheFirstArray(A, B, n);
}
}
 
// This code is contributed by avanitrachhadiya2155

<script>
// Make a set of maximum elements from two
// arrays A[] and B[]
function maximizeTheFirstArray(A, B, n)
{
 
    // Create copies of A[] and B[] and sort
    // the copies in descending order.
    let temp1 = new Array();
    let temp2 = new Array();
    for (let i of A)
    {
        temp1.push(i);
    }
    for (let i of B)
    {
        temp2.push(i);
    }
    temp1.sort((a, b) => a - b).reverse();
    temp2.sort((a, b) => a - b).reverse();
 
 
    // set maximum n distinct elements of
    // both sorted arrays in a map.
    let m = new Map();
    let i = 0, j = 0;
    while (m.size < n) {
        if (temp1[i] >= temp2[j]) {
            if (m.has(temp1[i])) {
                m.set(temp1[i], m.get(temp1[i]) + 1);
            }
            else {
                m.set(temp1[i], 1);
            }
            i++;
        }
        else {
            if (m.has(temp2[j])) {
                m.set(temp2[j], m.get(temp2[j]) + 1);
            }
            else {
                m.set(temp2[j], 1);
            }
            j++;
        }
    }
 
    // Copy elements of A[] to that
    // are present in hash m.
    let res = new Array();
    for (i = 0; i < n; i++)
        if (m.has(A[i]))
            res.push(A[i]);
 
    // Copy elements of B[] to that
    // are present in hash m. This time
    // we also check if the element did
    // not appear twice.
    for (i = 0; i < n; i++)
        if (m.has(B[i]) && m.get(B[i]) == 1)
            res.push(B[i]);
 
    // print result
    for (i = 0; i < n; i++)
        document.write(res[i] + " ");
}
 
// Driver program
let A = [9, 7, 2, 3, 6];
let B = [7, 4, 8, 0, 1];
let n = A.length;
maximizeTheFirstArray(A, B, n);
 
// This code is contributed by gfgking
 
</script>

9 7 6 4 8 

Complejidad de tiempo: O(n Log n)