Tutorialspoint.dev

Convert an array to reduced form | Set 2 (Using vector of pairs)

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}

We have discussed simple and hashing based solutions.

In this post, a new solution is discussed. The idea is to create a vector of pairs. Every element of pair contains element and index. We sort vector by array values. After sorting, we copy indexes to original array.

// 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 ";
    printArr(arr, n);
  
    convert(arr , n);
  
    cout << " Converted Array is ";
    printArr(arr, n);
  
    return 0;
}

Output :

Given Array is 
10 20 15 12 11 50 

Converted Array is 
0 4 3 2 1 5 

Time Complexity : O(n Log n)
Auxiliary Space : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter