Минимизировать массив, удалив все отдельные пары элементов

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

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

Примеры:

Input: A[] = {1, 7, 7, 4, 4, 4}, N = 6
Output: 0
Explanation: 3 pairs containing distinct elements can be formed from the array. Thus, no element left in the array.

Input: A[] = {25, 25}, N = 2
Output: 2
Explanation: No pairs containing distinct elements can be formed from the array. Thus, 2 elements left in the array.

Решение: выполните следующие шаги, чтобы решить эту проблему:

  • Создайте карту, скажем, mp , чтобы сохранить частоту каждого элемента в массиве. Пусть максимальная частота любого элемента равна m .
  • Если длина массива четная:
    • Обратите внимание, что если m меньше или равно ( N /2), то каждый элемент может образовать пару с другим. Таким образом, выведите 0.
    • В противном случае минимальный размер массива, т. е. количество элементов, оставшихся без пары, определяется выражением:
  • Если длина массива нечетная:
    • Обратите внимание, что если m больше или равно ( N /2), то всегда будет оставаться 1 элемент без какой-либо пары. Таким образом, выход 1.
    • В противном случае минимальный размер массива снова будет равен (2* mN ).

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


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

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