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

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

Пример:

Input: arr[] = {2, 2, 2, 2, 4, 4, 6, 7, 7, 3, 3, 3}
Output: 2
Explanation: First we select 2 and delete all its occurrences after that arr[] becomes – {4, 4, 6, 7, 7, 3, 3, 3} with size = 8. As the size is still greater than half, we select 3 and delete all its occurrences, after that arr[] becomes – {4, 4, 6, 7, 7} with size = 5.

Input: arr[] = {3, 3, 3, 3, 3}
Output: 1
Explanation : select 3 and remove all its occurrences.

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 4
Explanation : Since there is no duplicate elements, hence any 4 elements can be removed to make the array length at least half.

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

Следуйте инструкциям, чтобы решить проблему:

• Используйте Hash-map для хранения частоты элементов в присутствующем массиве.
• Сохраните частоты в списке.
• Отсортируйте список и пройдитесь по нему сзади.
• Выберите элемент с наибольшей частотой и уменьшите его от размера массива и увеличьте количество удаленных уникальных элементов.
• Если новый размер массива становится как минимум половиной исходного размера массива, вернуть количество уникальных элементов до сих пор.

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

Временная сложность : O(N*logN), сортировка списка частот
Вспомогательное пространство : O(N), хеш-карта для хранения частот

Другой эффективный подход (с использованием приоритетной очереди):

Мы можем решить проблему, используя очередь с приоритетом вместо сортировки по частоте элементов. Итак, мы инициализируем приоритетную очередь и сохраняем частоту каждого уникального элемента, который мы получаем из неупорядоченной карты . Затем мы запускаем цикл while и начинаем удалять элементы из очереди приоритетов, которые имеют самую высокую частоту, до самых низких частот в порядке убывания, и, следовательно, мы получаем количество элементов, подлежащих удалению. Временная сложность этого подхода составляет O (n * logn) , но это займет гораздо меньше времени, если элементы будут более частыми.

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

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