Преобразование массива в сокращенную форму с использованием вектора пар

Учитывая массив с n различными элементами, преобразуйте данный массив в форму, в которой все элементы находятся в диапазоне от 0 до n-1. Порядок элементов такой же, т.е. 0 ставится на место наименьшего элемента, 1 ставится на место второго наименьшего элемента, … n-1 ставится на место наибольшего элемента.

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

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

Мы обсудили простые решения и решения, основанные на хешировании.

В этом посте обсуждается новое решение. Идея состоит в том, чтобы создать вектор пар. Каждый элемент пары содержит элемент и индекс. Сортируем вектор по значениям массива. После сортировки мы копируем индексы в исходный массив.

Выход :

Given Array is 
10 20 15 12 11 50 

Converted Array is 
0 4 3 2 1 5 

Временная сложность: O (n Log n)
Вспомогательное пространство: O(n)

Эта статья предоставлена Арпитом Гуптой . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по адресу review-team@geeksforgeeks.org. Посмотрите, как ваша статья появится на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.