Convertir una array a forma reducida | Conjunto 1 (Simple y Hashing)

Dada una array con n elementos distintos, convierta la array dada en una forma donde 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 el 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}

La complejidad de tiempo esperada es O(n Log n).

// C++ program to convert an array in reduced
// form
#include <bits/stdc++.h>
using namespace std;
 
void convert(int arr[], int n)
{
    // Create a temp array and copy contents
    // of arr[] to temp
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));
 
    // Sort temp array
    sort(temp, temp + n);
 
    // Create a hash table. Refer
    // http://tinyurl.com/zp5wgef
    unordered_map<int, int> umap;
 
    // One by one insert elements of sorted
    // temp[] and assign them values from 0
    // to n-1
    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;
 
    // Convert array by taking positions from
    // umap
    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
 
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;
}

// Java Program to convert an Array
// to reduced form
import java.util.*;
 
class GFG
{
    public static void convert(int arr[], int n)
    {
        // Create a temp array and copy contents
        // of arr[] to temp
        int temp[] = arr.clone();
 
        // Sort temp array
        Arrays.sort(temp);
 
        // Create a hash table.
        HashMap<Integer, Integer> umap = new HashMap<>();
 
        // One by one insert elements of sorted
        // temp[] and assign them values from 0
        // to n-1
        int val = 0;
        for (int i = 0; i < n; i++)
            umap.put(temp[i], val++);
 
        // Convert array by taking positions from
        // umap
        for (int i = 0; i < n; i++)
            arr[i] = umap.get(arr[i]);
    }
 
    public static void printArr(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int arr[] = {10, 20, 15, 12, 11, 50};
        int n = arr.length;
 
        System.out.println("Given Array is ");
        printArr(arr, n);
 
        convert(arr , n);
 
        System.out.println("\n\nConverted Array is ");
        printArr(arr, n);
 
    }
}
 
// This code is contributed by Abhishek Panwar

# Python3 program to convert an array
# in reduced form
def convert(arr, n):
    # Create a temp array and copy contents
    # of arr[] to temp
    temp = [arr[i] for i in range (n) ]
     
    # Sort temp array
    temp.sort()
     
    # create a map
    umap = {}
     
     
    # One by one insert elements of sorted
    # temp[] and assign them values from 0
    # to n-1
    val = 0
    for i in range (n):
        umap[temp[i]] = val
        val += 1
     
    # Convert array by taking positions from umap
    for i in range (n):
        arr[i] = umap[arr[i]]
     
def printArr(arr, n):
    for i in range(n):
        print(arr[i], end = " ")
 
# Driver Code
if __name__ == "__main__":
    arr = [10, 20, 15, 12, 11, 50]
    n = len(arr)
    print("Given Array is ")
    printArr(arr, n)
    convert(arr , n)
    print("\n\nConverted Array is ")
    printArr(arr, n)
 
# This code is contributed by Abhishek Gupta

// C# Program to convert an Array
// to reduced form
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
    public static void convert(int []arr, int n)
    {
        // Create a temp array and copy contents
        // of []arr to temp
        int []temp = new int[arr.Length];
        Array.Copy(arr, 0, temp, 0, arr.Length);
 
        // Sort temp array
        Array.Sort(temp);
 
        // Create a hash table.
        Dictionary<int, int> umap =
            new Dictionary<int, int>();
 
        // One by one insert elements of sorted
        // []temp and assign them values from 0
        // to n - 1
        int val = 0;
        for (int i = 0; i < n; i++)
            if(umap.ContainsKey(temp[i]))
                umap[temp[i]] = val++;
            else
                umap.Add(temp[i], val++);
 
        // Convert array by taking positions from
        // umap
        for (int i = 0; i < n; i++)
            arr[i] = umap[arr[i]];
    }
 
    public static void printArr(int []arr, int n)
    {
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver code
    public static void Main(String[] args)
    {
 
        int []arr = {10, 20, 15, 12, 11, 50};
        int n = arr.Length;
 
        Console.WriteLine("Given Array is ");
        printArr(arr, n);
 
        convert(arr , n);
 
        Console.WriteLine("\n\nConverted Array is ");
        printArr(arr, n);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript Program to convert an Array
// to reduced form
 
    function convert(arr, n)
    {
        // Create a temp array and copy contents
        // of arr[] to temp
        let temp = [...arr];
   
        // Sort temp array
        temp.sort((a, b) => a - b);
   
        // Create a hash table.
        let umap = new Map();
   
        // One by one insert elements of sorted
        // temp[] and assign them values from 0
        // to n-1
        let val = 0;
        for (let i = 0; i < n; i++)
            umap.set(temp[i], val++);
   
        // Convert array by taking positions from
        // umap
        for (let i = 0; i < n; i++)
            arr[i] = umap.get(arr[i]);
    }
   
    function prletArr(arr, n)
    {
        for (let i = 0; i < n; i++)
            document.write(arr[i] + " ");
    }
 
// Driver program
 
         let arr = [10, 20, 15, 12, 11, 50];
        let n = arr.length;
   
        document.write("Given Array is " + "<br/>");
        prletArr(arr, n);
   
        convert(arr , n);
   
        document.write("<br/>" + "Converted Array is "  + "<br/>");
        prletArr(arr, n);
       
</script>