Сложность: easy
Дан массив целых чисел фиксированной длины arr, дублируйте каждое вхождение нуля, сдвигая оставшиеся элементы вправо.
Учтите, что элементы за пределами длины исходного массива не записываются. Внесите указанные изменения в массив на месте и ничего не возвращайте.
Пример:
Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
👨💻 Алгоритм:
1⃣Найдите количество нулей, которые будут продублированы, назовем это possible_dups. Необходимо убедиться, что мы не считаем нули, которые будут отброшены, так как отброшенные нули не будут частью итогового массива. Количество possible_dups даст нам количество элементов, которые будут отброшены из исходного массива. В любой момент времени length_ - possible_dups — это количество элементов, которые будут включены в итоговый массив.
2⃣Обработайте крайний случай для нуля, находящегося на границе оставшихся элементов. Будьте особенно внимательны при дублировании нулей в оставшемся массиве. Следует учитывать, лежит ли ноль на границе. Этот ноль может быть учтен с возможными дубликатами или может быть просто включен в оставшиеся элементы, когда не осталось места для его дубликата. Если он является частью possible_dups, мы хотим его дублировать, в противном случае — нет.
3⃣Итерируйте массив с конца и копируйте ненулевой элемент один раз, а нулевой элемент дважды. Когда мы говорим об отбрасывании лишних элементов, это означает, что мы начинаем с левой стороны лишних элементов и начинаем перезаписывать их новыми значениями, в конечном итоге сдвигая оставшиеся элементы вправо и создавая пространство для всех дублированных элементов в массиве.
😎 Решение:
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
possibleDups = 0
length_ = len(arr) - 1
for left in range(length_ + 1):
if left > length_ - possibleDups:
break
if arr[left] == 0:
if left == length_ - possibleDups:
arr[length_] = 0
length_ -= 1
break
possibleDups += 1
last = length_ - possibleDups
for i in range(last, -1, -1):
if arr[i] == 0:
arr[i + possibleDups] = 0
possibleDups -= 1
arr[i + possibleDups] = 0
else:
arr[i + possibleDups] = arr[i]
Ставь 👍 и забирай 📚 Базу знаний