Заменить все вхождения X на Y для запросов Q в заданном массиве

Опубликовано: 21 Сентября, 2022

Дан массив 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] из хэш -карты.
  • Теперь создайте новую переменную map = {} из значений hashmap .
  • Поменяйте местами пары ключ-значение, чтобы карта содержала пары ключ-значение в качестве индекса и значения ключа хэш-карты.
  • Используя эту карту , мы теперь можем обновить исходный массив arr , обновив значения в каждой позиции arr значением из map .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(max(N, Q)), где N — размер arr[], а Q — размер запроса[][].
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ