Заменить все вхождения X на Y для запросов Q в заданном массиве
Дан массив arr[] и двумерный массив query[][] , состоящий из запросов. Для каждого запроса q замените все вхождения query[i][0] в arr[] на query[i][1] .
Примеры:
Input: arr[] = {2, 2, 5, 1} query = {{2, 4}, {5, 2}}
Output: {4, 4, 2, 1}
Explanation: Following are the operations performed in the given array according to the queries given.
For first query {2, 4}, replace all occurrences of 2 in arr[] with 4. arr[] will be updated as arr[] = {4, 4, 5, 1}.
For second query {5, 2}, replace all occurrences of 5 with 2. arr[] will be updated as arr[] = {4, 4, 2, 1}.Input: arr[] ={2, 2, 5}, query = {{4, 5}, {2, 5}, {1, 3}, {2, 4}}
Output: {5, 5, 5}
Наивный подход: (решение грубой силы) Наивный подход состоял бы в том, чтобы перебирать все запросы query и для каждого query[i][0] находить все его вхождения в arr[] и заменять их на query[i ][1] .
Временная сложность: O(N*Q), где N — размер arr[], а Q — размер запроса[][].
Вспомогательное пространство: O(1)
Эффективный подход: лучшим решением было бы использование Hashmap, в котором хранятся индексы элемента в массиве. Выполните следующие шаги, чтобы решить данную проблему.
- Инициализируйте hashmap = {} и заполните его элементом массива в качестве ключа и списком, указывающим его положение в массиве.
- Повторить каждый запрос q запроса[][] .
- Если q[0] присутствует в hashmap ,
- Если q[1] присутствует в хэш -карте, то расширяем значение q[0] до значения ключа q[1] .
- В противном случае добавьте значение ключа q[1] со значением ключа q[0].
- Удалите пару ключ-значение для q[0] из хэш -карты.
- Если q[0] присутствует в hashmap ,
- Теперь создайте новую переменную map = {} из значений hashmap .
- Поменяйте местами пары ключ-значение, чтобы карта содержала пары ключ-значение в качестве индекса и значения ключа хэш-карты.
- Используя эту карту , мы теперь можем обновить исходный массив arr , обновив значения в каждой позиции arr значением из map .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(max(N, Q)), где N — размер arr[], а Q — размер запроса[][].
Вспомогательное пространство: O(N)