Минимизировать массив, удалив все отдельные пары элементов
Опубликовано: 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* m – N ).
Ниже приведена реализация приведенного выше кода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)