План курса / Все задачи / Алгоритмы и структуры данных

Перемещение нулей

легко

# решено

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

Необходимо изменять исходный массив напрямую, без создания нового массива для хранения результата.

Пример 1:

Ввод: nums = [2,1,0,0,4,0,9]
Вывод: [2,1,4,9,0,0,0]

Пример 2:

Ввод: nums = [0]
Вывод: [0]

Ограничения:

len(nums) >= 1

public class Solution
{
    public static List<int> MoveZeros(List<int> nums)
    {
        int p1 = 0; // Указывает на позицию, куда ставим следующий ненулевой элемент
        int p2 = 0; // Указывает на следующий ненулевой элемент

        while (p2 < nums.Count)
        {
            if (nums[p2] != 0)
            {
                (nums[p1], nums[p2]) = (nums[p2], nums[p1]);
                p1++;
            }
            p2++;
        }
        return nums;
    }
}

#include <vector>
using namespace std;

vector<int> moveZeros(vector<int>& nums) {
    // указывает на какую позицию поставим следующий элемент не равный 0
    int p1 = 0;
    // указывает на следующий не нулевой элемент
    int p2 = 0;
    while (p2 < nums.size()) {
        if (nums[p2] != 0) {
            swap(nums[p1], nums[p2]);
            p1++;
        }
        p2++;
    }
    return nums;
}

package main

func moveZeros(nums []int) []int {
    // указывает на какую позицию поставим следующий элемент не равный 0
    p1 := 0
    // указывает на следующий не нулевой элемент
    p2 := 0
    for p2 < len(nums) {
        if nums[p2] != 0 {
            nums[p1], nums[p2] = nums[p2], nums[p1]
            p1++
        }
        p2++
    }
    return nums
}

import java.util.*;

public class Solution {
    public static List<Integer> moveZeros(List<Integer> nums) {
        // указывает на какую позицию поставим следующий элемент не равный 0
        int p1 = 0;
        // указывает на следующий не нулевой элемент
        int p2 = 0;
        while (p2 < nums.size()) {
            if (nums.get(p2) != 0) {
                Collections.swap(nums, p1, p2);
                p1++;
            }
            p2++;
        }
        return nums;
    }
}

from typing import *

def move_zeros(nums: List[int]) -> List[int]:
    # указывает на какую позицию поставим следующий элемент не равный 0
    p1 = 0
    # указывает на следующий не нулевой элемент
    p2 = 0
    while p2 < len(nums):
        if nums[p2] != 0:
            nums[p1], nums[p2] = nums[p2], nums[p1]
            p1 += 1
        p2 += 1
    return nums

export function moveZeros(nums) {
    // указывает на какую позицию поставим следующий элемент не равный 0
    let p1 = 0;
    // указывает на следующий не нулевой элемент
    let p2 = 0;
    while (p2 < nums.length) {
        if (nums[p2] !== 0) {
            [nums[p1], nums[p2]] = [nums[p2], nums[p1]];
            p1++;
        }
        p2++;
    }
    return nums;
}

Оценка сложности

Время: O(n), где n - длина массива nums
Память: O(1)

На собеседовании могут изменить формулировку и попросить удалить все нули, сохранив порядок остальных элементов. В таком случае алгоритм останется тем же, но в конце нужно удалить нули из конца массива — только такое решение будет считаться оптимальным. Оценка по времени и памяти в таком случае не изменятся: O(n) и O(1).