283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

· You must do this in-place without making a copy of the array.

· Minimize the total number of operations.

283. Сдвинуть нули

Задан массив nums, реализуйте функцию, которая передвинет все 0 в его конец, сохранив относительный порядок ненулевых элементов.

Например, если nums = [0, 1, 0, 3, 12], то после вызова функции nums должно содержать [1, 3, 12, 0, 0].

· Обработку следует делать in-place, без создания копии массива.

· Минимизировать общее количество операций.

// C++

class Solution {

public:

void moveZeroes(vector<int>& nums) {

}

};

// Java

public class Solution {

public void moveZeroes(int[] nums) {

}

}

РЕШЕНИЕ

последовательности

Анализ алгоритма

Заведем два индекса: j двигается по числам массива, i указывает на позицию, куда будет переноситься ненулевой j-ый элемент. Если nums[j] = 0, то двигаем вперед только j. Если nums[j] ≠ 0, то устанавливаем nums[i] = nums[j] и двигаем вперед оба указателя на одну позицию.

Реализация алгоритма

class Solution

{

public:

void moveZeroes(vector<int>& nums)

{

int i, j;

for(i = j = 0; j < nums.size(); j++)

if (nums[j] != 0) nums[i++] = nums[j];

while(i < nums.size())

nums[i++] = 0;

}

};

Java реализация

public class Solution

{

public void moveZeroes(int[] nums)

{

int i, j;

for(i = j = 0; j < nums.length; j++)

if (nums[j] != 0) nums[i++] = nums[j];

while(i < nums.length)

nums[i++] = 0;

}

}