Encuentre solo un elemento estrictamente mayor de la primera array para cada elemento en la segunda array

Dadas dos arrays A[] y B[] que contienen N elementos, la tarea es encontrar, para cada elemento de la array B[] , el elemento que es estrictamente mayor que el elemento que está presente en la array A[] . Si no hay ningún valor presente, imprima ‘null’.

Nota: El valor de la array A[] solo se puede usar una vez. 

Ejemplos:  

Entrada: A[] = {0, 1, 2, 3, 4}, B[] = {0, 1, 1, 2, 3} 
Salida: 1 2 3 4 nulo 
Explicación: 
Al iterar cada elemento en la array B []: 
el valor que es estrictamente mayor que 0 y está presente en el arreglo A[] es 1. 
De manera similar, el valor que es estrictamente mayor que 1 y está presente en el arreglo A[] es 2. 
De manera similar, el valor que es estrictamente mayor que 1 y presente en el arreglo A[] es 3 porque 2 ya se usó para el 1 anterior. 
De manera similar, el valor que es estrictamente mayor que 2 y presente en el arreglo A[] es 4. 
Ahora, no hay valor en la array que es mayor que 3 porque 4 ya se ha utilizado para los 2 anteriores. Por lo tanto, se imprime nulo. 

Entrada: A[] = {0, 1, 6, 4, 0, 2, 4, 2, 4, 7}, B[] = {0, 1, 6, 4, 0, 2, 4, 2, 4 , 7} 
Salida: 1 2 7 6 2 4 nulo 4 nulo nulo 

Enfoque: La idea es utilizar la estructura de datos del conjunto de árboles . Pero dado que un conjunto de árboles no admite valores duplicados, se usa un mapa hash para almacenar la frecuencia de los elementos.  

• Iterar a través de la array A[] .
• Agregue los elementos de la array A[] al conjunto de árboles.
• Actualice sus frecuencias en el hashmap.
• Ahora, para cada elemento en la array B[], encuentre el valor que es estrictamente mayor que el valor actual usando la función superior() del conjunto de árboles.
• Ahora, reduzca la frecuencia de este número en el mapa hash en 1.
• Siga repitiendo los dos pasos anteriores hasta que la frecuencia de los números se convierta en 0. Si es 0, entonces todas las ocurrencias de ese número se han agotado para los elementos. Entonces, elimine ese elemento del conjunto de árboles.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find the values
// strictly greater than the element
// and present in the array
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the values
// strictly greater than the element
// and present in the array
void operations(int n, long long A[],
                       long long B[])
{
     
    // Treeset to store the
    // values of the array A
    set<long long>tree;
     
    // HashMap to store the frequencies
    // of the values in array A
    map<long long, int>freqMap;
 
    // Iterating through the array
    // and add values in the treeset
    for(int j = 0; j < n; j++)
    {
        long long x = A[j];
        tree.insert(x);
        freqMap[x]++;
    }
 
    // Finding the strictly greater value
    // in the array A[] using "higher()"
    // function and also reducing the
    // frequency of that value because it
    // has to be used only once
    for(int j = 0; j < n; j++)
    {
        long long  x = B[j];
 
        // If the higher value exists
        if (tree.upper_bound(x) != tree.end())
        {
            cout << *tree.upper_bound(x) << " ";
             
            // If the frequency value is 1
            // then remove it from treeset
            // because it has been used
            // and its frequency becomes 0
            if (freqMap[*tree.upper_bound(x)] == 1)
            {
                tree.erase(*tree.upper_bound(x));
            }
             
            // Else, reducing the frequency
            // by 1
            else
            {
                freqMap[*tree.upper_bound(x)]--;
            }
        }
 
        // If the value is not present
        // then print null
        else
        {
            cout << "null ";
        }
    }
}
 
// Driver code
int main()
{
    int n = 12;
    long long A[] = { 9, 5, 100, 4, 89, 2,
                      0, 2, 89, 77, 77, 77 };
    long long B[] = { 0, 18, 60, 34, 50, 29,
                      4, 20, 48, 77, 2, 8 };
     
    operations(n, A, B);
}
 
// This code is contributed by Stream_Cipher

// Java program to find the values
// strictly greater than the element
// and present in the array
 
import java.io.*;
import java.util.*;
public class GFG {
 
    // Function to find the values
    // strictly greater than the element
    // and present in the array
    public static void operations(
        int n, long A[], long B[])
    {
 
        // Treeset to store the
        // values of the array A
        TreeSet<Long> tree
            = new TreeSet<Long>();
 
        // HashMap to store the frequencies
        // of the values in array A
        HashMap<Long, Integer> freqMap
            = new HashMap<Long, Integer>();
 
        // Iterating through the array
        // and add values in the treeset
        for (int j = 0; j < n; j++) {
            long x = A[j];
            tree.add(x);
 
            // Updating the frequencies
            if (freqMap.containsKey(x)) {
 
                freqMap.put(x, freqMap.get(x) + 1);
            }
            else {
 
                freqMap.put(x, 1);
            }
        }
 
        // Finding the strictly greater value
        // in the array A[] using "higher()"
        // function and also reducing the
        // frequency of that value because it
        // has to be used only once
        for (int j = 0; j < n; j++) {
            long x = B[j];
 
            // If the higher value exists
            if (tree.higher(x) != null) {
                System.out.print(tree.higher(x) + " ");
 
                // If the frequency value is 1
                // then remove it from treeset
                // because it has been used
                // and its frequency becomes 0
                if (freqMap.get(tree.higher(x)) == 1) {
                    tree.remove(tree.higher(x));
                }
 
                // Else, reducing the frequency
                // by 1
                else {
                    freqMap.put(
                        tree.higher(x),
                        freqMap.get(tree.higher(x))
                            - 1);
                }
            }
 
            // If the value is not present
            // then print null
            else {
                System.out.print("null ");
            }
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
 
        int n = 12;
        long A[] = new long[] { 9, 5, 100, 4,
                                89, 2, 0, 2,
                                89, 77, 77, 77 };
        long B[] = new long[] { 0, 18, 60, 34,
                                50, 29, 4, 20,
                                48, 77, 2, 8 };
 
        operations(n, A, B);
    }
}

# Python program to find the values
# strictly greater than the element
# and present in the array
from typing import List
from bisect import bisect_right
 
# Function to find the values
# strictly greater than the element
# and present in the array
def operations(n: int, A: List[int], B: List[int]) -> None:
 
    # Treeset to store the
    # values of the array A
    tree = set()
 
    # HashMap to store the frequencies
    # of the values in array A
    freqMap = dict()
 
    # Iterating through the array
    # and add values in the treeset
    for j in range(n):
        x = A[j]
        tree.add(x)
        if x not in freqMap:
            freqMap[x] = 0
        freqMap[x] += 1
 
    # Finding the strictly greater value
    # in the array A[] using "higher()"
    # function and also reducing the
    # frequency of that value because it
    # has to be used only once
    for j in range(n):
        x = B[j]
 
        # If the higher value exists
        sset = sorted(list(tree))
        index = bisect_right(sset, x)
        if index < len(tree):
            print(sset[index], end=" ")
 
            # If the frequency value is 1
            # then remove it from treeset
            # because it has been used
            # and its frequency becomes 0
            if (freqMap[sset[index]] == 1):
                tree.remove(sset[index])
 
            # Else, reducing the frequency
            # by 1
            else:
                freqMap[sset[index]] -= 1
 
        # If the value is not present
        # then print null
        else:
            print("null", end=" ")
 
# Driver code
if __name__ == "__main__":
 
    n = 12
    A = [9, 5, 100, 4, 89, 2, 0, 2, 89, 77, 77, 77]
    B = [0, 18, 60, 34, 50, 29, 4, 20, 48, 77, 2, 8]
 
    operations(n, A, B)
 
# This code is contributed by sanjeev2552

2 77 77 77 89 89 5 100 null null 4 9

Complejidad de tiempo: O (N * log (N)) porque la inserción de un elemento toma log (N) en un conjunto de árboles.