【算法分析与设计】移动零

题目

给定一个数组?nums，编写一个函数将所有?0?移动到数组的末尾，同时保持非零元素的相对顺序。

请注意?，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

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

思路：

从前往后开始遍历，找到不为0就与前面的值进行交换，

直到交换到第一个回去不为0的值结束。

代码实现：

class Solution {
    public void moveZeroes(int[] nums) {
       int left=0;
       int right=nums.length-1;
       int temp=0;
        for(int i=0;i<nums.length;i++){
            for(int j=i;j>0;j--){
                if(nums[j-1]!=0){
                    break;
                }
                 temp=nums[j];
                 nums[j]=nums[j-1];
                 nums[j-1]=temp;
                
            
            }
        }
           
          
    }
}

击败5%的用户。。。

肯定不是这样写的，这样写时间复杂度应该到了nlogn了（emmm不会算）

想别的方法呃，。。。

ding ding ding dong 有了！！！

思路二：

可以利用双指针嘛。

left指针指向最初的位置

right从0开始遍历，找到不为0的数字就和left指针的值进行交换

之后left++;

最后right找到末尾后。直接将left右边的所有值置为0即可。

?开始都指向索引0的节点。

之后right++

?此时right指向索引为1的节点。这个节点的值为1就与left所指向的节点交换值之后，left++,right++

?发现right指向的为0，不处理下一个right++

发现right指向3 与left的节点值交换，left++.,right++?

之后right指向12 再交换，最后left的右边的所有节点置为0即可?

代码实现

class Solution {
    public void moveZeroes(int[] nums) {
       int left=0;

        for(int right=0;right<nums.length;right++){
            if(nums[right]!=0){
                nums[left]=nums[right];
                left++;
            }
        }
        for(int i=left;i<nums.length;i++){
            nums[i]=0;
        }
           
          
    }
}

nice! 通过成功