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

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

• Если arr[i] и arr[i+1] равны, то умножьте i ^-й (текущий) элемент на 2 и присвойте (i +1) ^-му элементу значение 0 .
• После применения всех условий переместите все нули в конец массива.

Примеры:

Input: N = 6,  arr[] = [1, 2, 2, 1, 1, 0]
Output: [1, 4, 2, 0, 0, 0]
Explanation: At i = 0: arr[0] and arr[1] are not the same, so we do nothing.
At i = 1: arr[1] and arr[2] are the same, so we multiply arr[1] with 2 and change its next element to 0.
array = [1, 4, 0, 1, 1, 0]
 At i = 2: arr[2] and arr[3] are not the same, so we do nothing.
At i = 3: arr[3] and arr[4] are the same, so we multiply arr[3] with 2 and change its next element to 
arr[] = [1, 4, 0, 2, 0, 0]
At i = 4: arr[4] and arr[5] are the same, so we multiply arr[4] with 2 and change its next element to 0.
arr[] = [1, 4, 0, 2, 0, 0]
After applying the above 2 conditions, shift all the 0’s to the right side of the array.
arr[]= [1, 4, 2, 0, 0, 0]

Input: N =2, arr[] = [0, 1]
Output: [1, 0]
Explanation: At i = 0: arr[0] and arr[1] are not same, so we do nothing.
No conditions can be applied further, so we shift all 0’s to right.
arr[] = [1, 0]

Подход: линейная итерация

The basic idea is to linearly iterate the array and check whether the conditions are satisfied or not and perform operations according to the conditions.

Иллюстрация:

Consider an array arr[] = {1, 2, 2, 1, 1, 0};

At i = 0: 
array[0] and arr[1] are not the same, so we do nothing.

At i = 1:
arr[1] and arr[2] are the same, so we multiply array[1] with 2 and change its next element to 0.
arr[] = [1, 4, 0, 1, 1, 0]

At i = 2:
arr[2] and arr[3] are not the same, so we do nothing.

At i = 3:
arr[3] and arr[4] are the same, so we multiply array[3] with 2 and change its next element to 0.
arr[]= [1, 4, 0, 2, 0, 0]

At i = 4:
arr[4] and arr[5] are the same, so we multiply array[4] with 2 and change it’s next element to 0.
arr[] = [1, 4, 0, 2, 0, 0]

After applying the above 2 conditions, shift all the 0’s to right side of the array.
arr[] = [1, 4, 2, 0, 0, 0]

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

• Пройдите через заданный массив от i = 0 до N-2 .
• Если i- ^й элемент равен следующему элементу, то
  • Умножьте текущий элемент на 2 arr[i]*2 .
  • Установите следующий элемент arr[i]+1 с 0 .
• Теперь сдвиньте вправо все 0.
  • Создайте счетчик переменной count для подсчета количества ненулевых элементов массива.
  • Если arr[i] не равен нулю, просто обновите массив с переменной-счетчиком arr[count++] = arr[i] .
• установить все нули в конце массива.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N), потому что мы повторяем массив два раза.
Вспомогательное пространство: O(1)

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам