Найдите сумму разности индексов с одинаковым значением для каждого элемента массива

Дан массив arr[] размера N . Задача состоит в том, чтобы найти массив размера N такой, что i- ^й элемент является суммой |i – j| для всех j таких, что arr[i] равно arr[j] .

Примеры:

Input: arr = {2, 1, 4, 1, 2, 4, 4}
Output: {4, 2, 7, 2, 4, 4, 5}
Explanation:
=> Index 0: Another 2 is found at index 4. |0 – 4| = 4
=> Index 1: Another 1 is found at index 3. |1 – 3| = 2
=> Index 2: Two more 4s are found at indices 5 and 6. |2 – 5| + |2 – 6| = 7
=> Index 3: Another 1 is found at index 1. |3 – 1| = 2
=> Index 4: Another 2 is found at index 0. |4 – 0| = 4
=> Index 5: Two more 4s are found at indices 2 and 6. |5 – 2| + |5 – 6| = 4
=> Index 6: Two more 4s are found at indices 2 and 5. |6 – 2| + |6 – 5| = 5

Input: arr = {1, 10, 510, 10}
Output: {0 2 0 2}

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

Iterate over the array and for each element run another loop for finding the similar elements, if similar elements found then keep sum of difference between their indices. 

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Инициализировать результат массива для хранения ответов
• Запустите цикл для i = 0 до n – 1 (включительно)
  • Инициализировать переменную sum = 0;
  • Запустите еще один цикл для j = 0 до n – 1 (включительно)
    • Проверить, равен ли arr[i] arr[j]
    • Добавьте абсолютную разницу между их индексами в сумму
  • Вставьте сумму в результат .
• Наконец, верните результат .

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

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

Подход с использованием хеширования:

Keep track of frequency and sum of the index of similar elements. Iterate over the array and calculate the sum of indices to the left of the current index which is similar to the current element. 

Similarly, calculate the sum of indices to the right of the current index which is similar to the current element. The result for the i^th index would be the sum of all the differences. 

Иллюстрация:

Consider the arr = {1, 2, 1, 1, 2, 1}

Now, If have to calculate the result for the index i = 3 which is element 1.

• To calculate the absolute value of the required result from the left would be something like => (i – 0) + (i – 2), which is equals to (2 * i – (0 + 2)). 
• To generalise these, we can generate a formula to do the same: (frequency of similar element to the left* i) – (Sum of occurances of such indices).
• To calculate the absolute value of required result from the right would be something like => (5 – i)
  To generalise these, we can generate a formula to do the same: (Sum of occurances of such indices) – (frequency of similar element to the right* i)
• We can conclude from the above that: The result for the i^th index would be:
  result[i] = ((leftFreq * i) – leftSum) + (rightSum – (rightFreq * i)).

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Объявите неупорядоченную карту unmap , где ключ — это элемент , а соответствующее значение — это пара, состоящая из общей частоты и общей суммы .
• Объявите неупорядоченную карту unmap2 , где ключ — это элемент , а соответствующее значение — это пара, состоящая из частоты до любого индекса i и суммы до i- ^го индекса .
• Переберите массив и обновите unmap .
• Объявить массив result[] для хранения результата
• Итерация по заданному массиву
  • Обновите результат[i] значением, указанным выше.
  • Обновите unmap2 , увеличив частоту текущего элемента и сумму всех вхождений подобных элементов до i- ^го индекса.
• Наконец, верните результат [] в качестве требуемого ответа.

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

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Введение в хэширование — учебные пособия по структурам данных и алгоритмам