算法题4：移动零

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 
示例 1:

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

示例 2:

输入: nums = [0]
输出: [0]

 
提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

思路：

参考网友的思路，用双指针的方法，维护两个下标（假设两个人）同时从左到右依次往前走，当右侧下标的位置不是0时就把两个下标位置的数互换，
这个规则在不存在0的情况下两个人的步伐是一致的，当遇到0的时候左侧那个人就会慢下来，右侧的下标每遍历一次就往前走一步，而左侧的只有遇到非0数才会往前走一步，这样就出现了如下数据的情况：

[0,1,0,3,12] i=0 left = 0 不操作
[0,1,0,3,12] i=1 left = 0 nums[i],[nums][left]换位 left ++
[1,0,0,3,12] i=2 left = 1 不操作
[1,0,0,3,12] i=3 left = 1 nums[i],[nums][left]换位 left ++
[1,3,0,0,12] i=4 left = 2 nums[i],[nums][left]换位 left ++
[1,3,12,0,0] 

左边的人遇到0就会站住那里，然后右边的人遇到非0就会跟他交换，然后左边的人再往前走一步，数据变化的规律可以看到两个人在走着的时候中间的位置都是0，直到右边的人把最后一个非0的数换过来，这样就达到了题目的要求把所有的0都换到了右边，非0数的顺序也没变

 

python：

class Solution:
    def moveZeroes(self,nums) -> None:
        left = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[left], nums[i] = nums[i], nums[left]
                left += 1
        return nums

结果：

 

 

Java：

class Solution {
    public void moveZeroes(int[] nums) {
       int left =0;
       int n = nums.length;
       for (int i=0; i< n; i ++) {
        if (nums[i] != 0) {
            // 交换nums[i] 和 [nums][left]
            int tmp = nums[i];
            nums[i] = nums[left];
            nums[left] = tmp;
            left ++;
        }
       }
    }
}

结果：