Минимизируйте операции по очистке массива, удалив два неравных элемента или один элемент

Опубликовано: 25 Февраля, 2023

Дан массив A размера N, задача состоит в том, чтобы найти минимальное количество операций, необходимых для того, чтобы сделать массив A пустым. Могут быть выполнены следующие операции:

  • Выберите любые два элемента, скажем, X и Y , из A такие, что X != Y , и удалите их.
  • В противном случае выберите любой элемент, скажем, X , из A и удалите его.

Примеры:

Input: N = 2, A = {2, 2}
Output: 2
Explanation: Remove both values separately and 
it will cost a total of 2 operations.

Input: N = 2, A = {1, 2}
Output: 1
Explanation: Remove both values together in one operation 
and it will cost a total of 1 operation.

Input: N = 6, A = {2, 2, 2, 2, 3, 3}
Output: 4
Explanation: Remove A[0] and A[5] to get A = {2, 2, 2, 3}. 
Remove A[0] and A[3] to get A = {2, 2}. 
Remove A[0] to get A = {2}. 
Remove A[0] to get A = {}.

Подход: Проблема может быть решена на основе следующего наблюдения:

It can be observed that if any two elements can be removed simultaneously then it’s best to choose a pair with {Element with maximum frequency, Element with second maximum frequency} at each operation. The last remaining element has to be checked if it can be matched with any non-equal element pairs that are already formed.

Eventually, If the pairs come to be equal then we have exhausted all pairs with different elements and only equal elements are remaining which can only be removed using separate operations.

Выполните указанные шаги, чтобы решить проблему:

  • Перейдите массив A[] и сохраните все частоты в карте freq .
  • Вставьте все пары {частота, элемент} в массив пар (скажем, arrPos[] ).
  • Сортировка arrPos по частоте.
  • Пройдите arrPos в обратном порядке (скажем, i ) с j = i – 1 .
    • Перемещайтесь во вложенном порядке до тех пор, пока частота в arrPos[i] не будет равна 0 и j ≥ 0 .
      • Сохраните все сформированные пары в паре массивов (например , optimalPairs[] ).
      • Добавьте минимум частоты в arrPos[i] и arrPos[j] к OpCnt .
      • Вычтите минимум частоты в arrPos[i] и arrPos[j] из частоты arrPos[i] и arrPos[j] и уменьшите j .
  • Снова пройдите через arrPos[] , чтобы найти ненулевую частоту, и сделайте перерыв после добавления этой частоты в arrPos[i] к OpCnt .
  • Пройдите через пару optimalPairs и уменьшите OpCnt на 1 , а частоту в arrPos[i] на 2 , если оставшийся элемент в arrPos[i] не равен паре в optimalPairs .
  • Верните OpCnt в качестве окончательного ответа.

Ниже приведена реализация этого подхода:

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

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