Преобразование массива в сокращенную форму с использованием вектора пар
Учитывая массив с 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, и помогите другим гикам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.