Given an array of n elements, replace each element of the array by its corresponding rank. The rank of the lowest element is 1 and the highest element is n. Take a look at the example given below:
Input : 2, 5, 3, 7, 6 Output: 1, 3, 2, 5, 4 Explanation: Since 2 is the smallest element in the array, its rank is 1, 3 is the second smallest element its rank is 2 and so on.
Solution
The easiest way to solve this problem would be to iterate over the array and store the elements in a sorted map. The map would contain the element as key and the index of the element as the value.
Once we are done iterating over the array, we can just iterate over the sorted map. This will give us all the elements present in the sorted map in ascending order and we can fill up the rank of each element
Solution Implementation
#include <bits/stdc++.h>
using namespace std;
// Function to replace each element of the array by its rank in the array
void transform(vector<int>& arr)
{
// create an empty ordered map
map<int, int> map;
// store (element, index) pair in the map
for (int i = 0; i < arr.size(); i++)
map[arr[i]] = i;
// keys are stored in sorted order in ordered map
// rank starts from 1
int rank = 1;
// iterate through the map and replace each element by its rank
for (auto i: map)
arr[i.second] = rank++; // i.second stores the index of element i
}
int main()
{
vector<int> arr = { 10, 8, 15, 12, 6, 20, 1 };
// transform the array
transform(arr);
// print the transformed array
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
return 0;
}
