Convert an array to reduced form - GeeksforGeeks

Convert an array to reduced form - GeeksforGeeks
Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, … n-1 is placed for largest element.

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

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

Expected time complexity is O(n Log n).

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]];

}

Read full article from Convert an array to reduced form - GeeksforGeeks