Преобразование массива в сокращенную форму с помощью хэширования

Дан массив с 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}

Наивный подход:

A simple solution is to first find the minimum element, replace it with 0, consider the remaining array and find the minimum in the remaining array and replace it with 1, and so on.

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

Эффективный подход:

The idea is to sort the given array and use an unordered map to store the reduced form of each value of array then update the whole array to its reduced form using values from unordered map.

Для реализации идеи выполните следующие шаги:

• Создайте временный массив и скопируйте содержимое данного массива в temp[].
• Сортировать temp[] в порядке возрастания.
• Создайте пустую хеш-таблицу.
• Пройдите temp[] слева направо и сохраните сопоставление чисел и их значений (в преобразованном массиве) в хеш-таблице.
• Пройдите по заданному массиву и измените элементы на их позиции, используя хеш-таблицу.

Ниже приведены реализации вышеупомянутой идеи.

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

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

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