Convertir una array a forma reducida | Conjunto 2 (Usando vector de pares)

Dada una array con n elementos distintos, convierta la array dada en una forma en la que todos los elementos estén en el rango de 0 a n-1. El orden de los elementos es el mismo, es decir, 0 se coloca en lugar del elemento más pequeño, 1 se coloca para el segundo elemento más pequeño, … n-1 se coloca para el elemento más grande.

Input:  arr[] = {10, 40, 20}
Output: arr[] = {0, 2, 1}

Input:  arr[] = {5, 10, 40, 30, 20}
Output: arr[] = {0, 1, 4, 3, 2}

Hemos discutido soluciones simples y basadas en hashing .

En esta publicación, se discute una nueva solución. La idea es crear un vector de pares. Cada elemento de par contiene elemento e índice. Ordenamos el vector por valores de array. Después de ordenar, copiamos los índices a la array original.

// C++ program to convert an array in reduced
// form
#include <bits/stdc++.h>
using namespace std;
  
// Converts arr[0..n-1] to reduced form.
void convert(int arr[], int n)
{
    // A vector of pairs. Every element of
    // pair contains array element and its
    // index
    vector <pair<int, int> > v;
  
    // Put all elements and their index in
    // the vector
    for (int i = 0; i < n; i++)
        v.push_back(make_pair(arr[i], i));
  
    // Sort the vector by array values
    sort(v.begin(), v.end());
  
    // Put indexes of modified vector in arr[]
    for (int i=0; i<n; i++)
        arr[v[i].second] = i;
}
  
// Utility function to print an array.
void printArr(int arr[], int n)
{
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
  
// Driver program to test above method
int main()
{
    int arr[] = {10, 20, 15, 12, 11, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
  
    cout << "Given Array is \n";
    printArr(arr, n);
  
    convert(arr , n);
  
    cout << "\n\nConverted Array is \n";
    printArr(arr, n);
  
    return 0;
}

Producción :

Given Array is 
10 20 15 12 11 50 

Converted Array is 
0 4 3 2 1 5 

Complejidad de Tiempo : O(n Log n)
Espacio Auxiliar : O(n)

Este artículo es una contribución de Arpit Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.