LC283.移动零

题目地址(283. 移动零)

https://leetcode-cn.com/problems/move-zeroes/

题目描述

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

示例:

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

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

前置知识

• 双指针

公司

• Facebook 、字节跳动、微软、苹果等

思路

这个题本身并不难，使用暴力循环比较一定能做出来，而且代码逻辑也不复杂，但是效率非常的低，这里采用另一种思路：使用双指针，即设置一个pre和last两个指针，pre指向首部，last指向尾部。在正式比较前可以使用两个指针缩短一下比较范围，当首部有非零数时，pre指针向右移动，当尾部有零时，last向左移动。正式比较时，最外层循环代表要比较的数，注意这里不要直接i++，这样出现一个问题：当两个连续的零在一起的时候，第一个零正常移动到最后时，i此时停留在1处，然而第二个零已经到了i=0的位置上了，这样就会出现遗漏的情况。进入第二层循环的时候，就是进行换位的操作，这里也有一个比较坑的点，就是j要从i开始，不能从0开始，否则会出现把第0号元素给调换，但实际上根据逻辑，i之前的已经全部是非零数了（只有非零，i才会++），切记j从i开始，然后每一次将零换到最后，last都向前移动一个，下次就不用比较了，直到最后。

关键点

• 注意两次循环的循环条件

代码

• 语言支持：Java

Java Code:

class Solution {
    public void moveZeroes(int[] nums) {
        int pre,last;
        pre=0;
        last=nums.length-1;
        // if(nums[last]==0) last--;
        while(nums[last]==0&&last>0){
            last--;
        }
        while(nums[pre]!=0&&pre<last){
            pre++;
        }
        for(int i=0;i<=last;){
            if(nums[i]==0){
                for(int j=i;j<last;j++){
                    nums[j]+=nums[j+1];
                    nums[j+1]=nums[j]-nums[j+1];
                    nums[j]=nums[j]-nums[j+1];
                }
                last--;
            }
            else {i++;}
        }
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$