Решение задачи 283 “Перемещение нулей” с LeetCode.

Условие задачи

Дан массив nums целых чисел. Необходимо написать функцию, которая переместит все нули в конецй массива, а остальные числа ( ненулевые ) остануться в прежнем порядке.

дополнительные условия

• Необходимо решить задачу без использования дополнительного места – не создавать новый массив
• Минимизировать количество операций

пример

1
2

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Решения

С использованием дополнительного массива

Не смотря на то, что есть дополнительное условие - не создавать новый массив - предлагаю всё-таки рассмотреть это решение.

Идея алгоритма:

• заводим новый пустой массив
• создаем счетчик - кол-во нулей в исходном массиве
• идем по исходному массиву
  • если элемент ненулевой - добавляем элемент в новый массив в конец
  • если элемент нулевой - увеличиваем счетчик нулей
• когда дошли до конца исходного массива, добавляем в конец нового массива столько нулей, сколько в счетчике

Сложность

По памяти: O(n) По операциям: O(n)

Указатель на последний ненулевой элемент, свдиг ненулевых элементов

Идея алгоритма:

• завести указательно на последний ненулевой элемент ( указать на начальный элемент массива )
• пройти по массиву, если текущий элемент ненулевой :
  • записать его в позицию последнего ненулевого элемента
  • передвинуть указатель последнего ненулевого элемента и передвинуть на следующий элемент
• после прохода указатель на последний ненулевой элемент будет указывать на позицию с которой необходимо записывать нулевые элементы, для этого идем по массиву с позиции последнего ненулевого до конца массива и записываем нули

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func moveZeroes(nums []int)  {    
    start := 0
    for idx := range nums{    
        if nums[idx]!=0 {
            nums[start] =  nums[idx] 
            start++
        }       
    }  
    for jdx := start; jdx< len(nums);jdx++ {
        nums[jdx] = 0
    }
}

Сложность

По памяти: O(1) По операциям: O(n)

Указатель на последний ненулевой элемент, обмен нулевого и ненулевого

Идея алгоритма:

• завести указательно на последний ненулевой элемент ( указать на начальный элемент массива )
• пройти по массиву, если текущий элемент ненулевой :
  • обмениваем текущий с последним ненулевым
  • передвинуть указатель последнего ненулевого элемента и передвинуть на следующий элемен

1
2
3
4
5
6
7
8
9

func moveZeroes(nums []int)  {    
    start := 0
    for idx := range nums{    
        if nums[idx]!=0 {
            nums[start], nums[idx] = nums[idx], nums[start]
            start++
        }       
    }  
}

Сложность

По памяти: O(1) По операциям: O(n)

Забавное наблюдение

В этом решении кол-во операций меньше, чем в предыдущем решение, но из-за медленной работы операции обмена – это решение будем работать чуточку дольше