Минимизируйте удаления, чтобы ни один элемент массива с четным индексом не совпадал со следующим элементом.

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

Учитывая массив arr[] , задача состоит в том, чтобы найти минимальное количество требуемых операций удаления, чтобы:

  • Вновь созданный массив должен иметь четную длину.
  • arr[i] ≠ arr[i+1] для каждого i, где i%2==0 .

Примеры:

Input: arr[] = {1, 1, 2, 3, 5}
Output: 1
Explanation: Delete the first or second element of the array to satisfy the conditions.

Input: arr[] = {1, 1, 2, 2, 3, 3}
Output: 2
Explanation: Delete first element as the next element is a duplicate and the current index is even. 
Need to delete another element from the newly created array because 
the size of the newly created array is odd. arr = {1, 2, 2, 3, 3}
Delete the last element to make its length even. So the total number of operations is 2.

Подход: Общая идея решения этой проблемы заключается в следующем:

Maximize the number of elements in the newly created array and keep on checking if any even index element has the same value as the one  just next to it. 

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

  • Создайте стек пар для хранения элементов и индекса элемента в новом массиве.
  • Перебрать массив arr[] от i = 0 до N-1 :
    • Если индекс самого верхнего элемента стека нечетный, то поместите текущий элемент вместе с его индексом в новый массив стека.
    • В противном случае проверьте, совпадают ли значения arr[i] и самого верхнего элемента.
      • Если они одинаковы, перейдите к следующему элементу arr[] .
      • В противном случае добавьте текущий элемент в новый массив. индексный указатель на стек.
  • Наконец, если размер стека нечетный, удалите из стека еще один элемент.
  • Верните значение N — размер стека в качестве ответа, потому что это минимальное количество требуемых удалений.

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

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

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