58 移动零（Move Zeroes）

1 题目

题目：移动零（Move Zeroes）
描述：给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序。

1.必须在原数组上操作
2.最小化操作数

lintcode题号——539，难度——easy

样例1：

输入: nums = [0, 1, 0, 3, 12],
输出: [1, 3, 12, 0, 0].

样例2：

输入: nums = [0, 0, 0, 3, 1],
输出: [3, 1, 0, 0, 0].

2 解决方案

2.1 思路

  使用两个指针，一个指针从左向右指示当前的需要填充的位置，一个指针用于从左向右找非零的数，然后不断地将非零的数向前填充即可。

2.2 时间复杂度

  时间复杂度为O(n)。

2.3 空间复杂度

  空间复杂度为O(1)。

3 源码

细节：

1. 同向双指针法，left从左往右一步一步走，right从左往右依次寻找非零数，依次将非零的数填充到left位置。

C++版本：

/**
* @param nums: an integer array
* @return: nothing
*/
void moveZeroes(vector &nums) {
    // write your code here
    if (nums.empty())
    {
        return;
    }

    int left = 0;
    int right = 0;
    while (right < nums.size())
    {
        if (nums.at(right) != 0)
        {
            swap(nums.at(left), nums.at(right));
            left++;
        }

        right++;
    }
}