Genere una array usando condiciones dadas de una array dada

Dada una array arr[] de tamaño N , la tarea es construir una nueva array B[] usando elementos de la array A tal que: 
 

1. Si el elemento no está presente en B[] , agréguelo al final.
2. Si el elemento está presente en B[] , primero incremente su aparición más a la izquierda en 1 y luego agregue este elemento al final de la array.

Ejemplos: 
 

Entrada: arr[] = {1, 2, 1, 2} 
Salida: { 3, 2, 1, 2 } 
Explicación: 
arr[0] = 1, B = {}. 1 no está presente en B. Así que agréguelo al final. Por lo tanto, B = {1} 
arr[1] = 2, B = {1}. 2 no está presente en B. Así que agréguelo al final. Por lo tanto, B[] = {1, 2} 
arr[2] = 1, B = {1, 2}. 1 ya está presente en B[]. Así que incrementa B[0] en 1 y agrega 1 al final. Por lo tanto B[] = {2, 2, 1} 
arr[3] = 2, B = {2, 2, 1}. 2 ya está presente en B[]. Así que incrementa B[0] en 1 y agrega 2 al final. Por lo tanto B[] = {3, 2, 1, 2}
Entrada: arr[] = {2, 5, 4, 2, 8, 4, 2} 
Salida: {3, 5, 5, 3, 8, 4, 2} 
 

Enfoque ingenuo: para cada elemento en la array A, verifique si está presente en la array B o no. Si el elemento existe, incremente la aparición más a la izquierda en uno. Finalmente, agregue el elemento al final de la array B[]. 
Complejidad temporal: O(N ² )
Enfoque eficiente: La idea es usar un mapa para almacenar todos los índices de cada elemento. La array B[] se genera como: 
 

• Para cada elemento de la array arr[] , se comprueba si el elemento ya está presente en la array B[] o no.
• Si el elemento no está presente en la array B[] , entonces el elemento se agrega a la array B[] y su índice se agrega al mapa . Dado que esta es la primera aparición del elemento, este índice se convierte en el índice más a la izquierda del elemento.
• Si el elemento ya está presente en la array B[] , se devuelve el índice más a la izquierda y el elemento en ese índice se incrementa en uno. Cuando se incrementa el valor, el índice más a la izquierda del valor anterior se actualiza junto con el índice del nuevo valor.

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

// C++ program to generate an array
// from a given array under the
// given conditions
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate an array
// from a given array under the
// given conditions
void newArray(int A[], int n)
{
    // To maintain indexes of the
    // elements in sorted order
    unordered_map<int, set<int> > idx;
 
    // Initialize new array B
    std::vector<int> B;
 
    // For every element in the given
    // array arr[]
    for (int i = 0; i < n; ++i) {
 
        // Check if the element is present
        // in the array B[]
        if (idx.find(A[i]) != idx.end()) {
 
            // Get the leftmost position
            // in the array B
            int pos = *idx[A[i]].begin();
 
            // Remove the leftmost position
            idx[A[i]].erase(idx[A[i]].begin());
 
            // Increment the value at
            // the leftmost position
            B[pos]++;
 
            // Insert new value position
            // in the map
            idx[B[pos]].insert(pos);
        }
 
        // Append arr[i] at the end
        // of the array B
        B.push_back(A[i]);
 
        // Insert its position in hash-map
        idx[A[i]].insert(i);
    }
 
    // Print the generated array
    for (int i = 0; i < n; ++i)
        cout << B[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 1, 2 };
    int n = sizeof(arr) / sizeof(int);
 
    newArray(arr, n);
 
    return 0;
}

3 2 1 2

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)