Максимальное количество пар отдельных элементов массива, возможное путем включения каждого элемента только в одну пару

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

Примеры:

Input: arr[] = {4, 5, 4, 5, 4}
Output: 2
Explanation:
There can be 2 pairs forms from the given array i.e., {{4, 5}, {4, 5}}. Therefore, print 2.

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

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

• Инициализируйте карту, скажем, M , которая хранит частоту элементов массива.
• Инициализируйте приоритетную очередь, скажем, PQ , для реализации MaxHeap и вставьте в нее все частоты.
• Инициализируйте переменную, скажем, count как 0 , которая хранит максимальное количество результирующих пар.
• Пройдите приоритетную очередь PQ , пока ее размер не станет больше 1 , и выполните следующие шаги:
  • Вытолкните два верхних элемента из PQ.
  • Уменьшите значение извлеченного элемента на 1 и снова вставьте оба элемента в PQ .
  • Увеличьте значение count на 1 .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

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

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

Другой подход:

Эту проблему также можно решить, просто сохранив частоту каждого элемента в массиве. После этого нам нужно найти максимальную частоту элемента в заданном массиве. Подтверждено, что пара не может иметь одинаковые значения. Предположим, у нас есть элементы arr[]={1,1,1,1,2}, тогда будет сформирована одна пара, так как в массиве присутствуют два разных значения. Следовательно, пары не могут быть образованы, если у нас остался элемент с одинаковыми значениями.

Ниже приведена реализация:

Временная сложность этого подхода составляет O (N), поскольку мы проходим через все элементы, чтобы сформировать массив частот.
Вспомогательное пространство равно O(N).