Разница в количестве различных элементов слева и справа для каждого элемента массива

Учитывая массив arr[] , состоящий из N целых чисел, задача для каждого элемента массива состоит в том, чтобы найти абсолютную разницу между количеством различных элементов слева и справа от него в данном массиве arr[] .

Примеры:

Input: arr[] = {7, 7, 3, 2, 3}
Output: 2 2 0 1 2
Explanation:
Count of distinct elements that occur to the left of every index is given by [0, 0, 1, 1, 2] and the number of distinct elements that occur to the right of every index is [2, 2, 1, 0, 0]. Taking absolute difference of both gives the above output.

Input: arr[] = {4, 3, 2, 3}
Output: 2 0 1 2

Наивный подход: данная проблема может быть решена с использованием структуры данных набора, идея состоит в том, чтобы выполнить итерацию по диапазону [0, i – 1] , чтобы найти количество различных элементов слева от каждого элемента и аналогичным образом пройти массив по всему массиву. диапазон [i + 1, N – 1] , чтобы найти различные элементы справа от каждого элемента. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте массив res[] , в котором хранится результирующая абсолютная разница отдельных элементов для каждого элемента массива.
• Пройдите по заданному массиву и для каждого элемента по индексу i выполните следующие операции:
  • Переберите диапазон [0, i – 1] и вставьте все элементы в набор, скажем, S1 .
  • Переберите диапазон [i + 1, N – 1] и вставьте все элементы в набор, скажем, S2 .
  • Обновите значение res[i] как абсолютную разницу размеров наборов S1 и S2 .
• После выполнения вышеуказанных шагов выведите в качестве результата массив res[] .

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, сохраняя частоту отдельных элементов слева и справа для каждого элемента массива, а затем находя результирующую разницу для каждого элемента массива. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте две unordered_map , leftMap и rightMap , чтобы хранить отдельные элементы слева и справа от каждого индекса соответственно.
• Пройдите по данному массиву и вставьте все элементы массива в rightMap .
• Пройдите по заданному массиву, используя переменную i , и выполните следующие шаги:
  • Подсчитайте отдельные элементы слева от текущего элемента (скажем, countLeft ) как размер карты leftMap .
  • Уменьшите частоту текущего элемента карты rightMap на 1 .
  • Подсчитайте отдельные элементы справа от текущего элемента (скажем, countRight ) как размер карты rightMap .
  • Увеличьте частоту текущего элемента на карте leftMap на 1 .
  • Вставьте значение абсолютной разницы размеров карт leftMap и rightMap .
• После выполнения вышеуказанных шагов выведите в качестве результата массив res[] .

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

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