Подсчет неупорядоченных пар одинаковых элементов для всех подмассивов

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

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти общее количество неупорядоченных пар (i, j) в массиве, такое что arr[i] равно arr[j] и i < j для всех подмассивов заданного массива.

Примеры:

Input: arr[] = {1, 2, 1, 1}
Output: 6
Explanation: All subarrays of the given array of size greater than 1 are:

  1. {1, 2}: There are no such pairs satisfying the given criteria. Hence, the count of pairs for the current subarray is 0.
  2. {2, 1}: There are no such pairs satisfying the given criteria. Hence, the count of pairs for the current subarray is 0.
  3. {1, 1}: The pairs satisfying the given criteria are (0, 1). Hence, the count of pairs for the current subarray is 1.
  4. {1, 2, 1}: The pairs satisfying the given criteria are (0, 2). Hence, the count of pairs for the current subarray is 1.
  5. {2, 1, 1}: The pairs satisfying the given criteria are (1, 1). Hence, the count of pairs for the current subarray is 1.
  6. {1, 2, 1, 1}: The pairs satisfying the given criteria are (0, 2), (0, 3), and (2, 3). Hence, the count of pairs for the current subarray is 3.

Therefore, the total count from all the subarrays = 1 + 1 + 1 + 3 = 6.

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

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные подмассивы размера больше 1 и найти сумму количества пар, удовлетворяющих заданным критериям, для всех возможных подмассивов данного массива.

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

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

  • Инициализируйте карту M как имеющую ключи в виде пары и значения в виде вектора.
  • Инициализируйте другую переменную, скажем , как 0 , которая хранит общее количество пар, удовлетворяющих заданным критериям.
  • Пройдите по заданному массиву arr[] с помощью переменной i и добавьте значение i к ключу M[arr[i]] .
  • Перейдите карту M и выполните следующие шаги:
    • Инициализируйте вектор, скажем, V как значение, соответствующее текущему ключу.
    • Инициализируйте переменную, скажем, sum как 0 .
    • Пройдите заданный вектор V для каждого элемента V[j] , добавьте значение (sum*(N – V[j])) к переменной ans и добавьте значение (V[j] + 1) к переменной sum .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

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

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

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