【Leetcode题】283. 移动零

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

例如

 定义 nums = [0, 1, 0, 3, 12]，调用函数之后， nums 应为 [1, 3, 12, 0, 0]。

注意事项:

必须在原数组上操作，不要为一个新数组分配额外空间。
尽量减少操作总数。

我第一次提交的答案:【耗时20ms】

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0) {
            return;
        }
        int j = nums.length;
        for(int i=0;i<j;){
            if(nums[i] == 0) {
                //(i,j)之间的数字前移
                for(int k=i+1;k<j;k++){
                    nums[k-1] = nums[k];
                }
                //移至末尾
                nums[j-1] = 0;
                j--;
                continue;
            }
            i++;
        }
    }
}

很明显，我是从前到后遍历的，出现在后面的0也会前移，所以从后面遍历，就不会出现0前移的情况。

第二次提交的答案:【耗时18ms】

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0) {
            return;
        }
        //定义j表示后面非0的索引
        int j = nums.length - 1;
        for(int i=nums.length-1;i>=0;){
            if(nums[i] == 0){
                //需要换位置
                if(i < j){
                    for(int k=i+1;k<=j;k++){
                        nums[k-1] = nums[k];
                    }
                    nums[j] = 0;
                }
                j--;
            }
            i--;           
        }
        
    }
}

继续优化

目前的做法是，没找到一个0,就执行移动操作，这个会导致同一个数字都移动多次。

思维要打开，题目讲的是0要后移，其反意就是非0元素前移。

第三次提交答案： 【耗时2ms】

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0){
            return;
        }
        //记录非o元素开始位置
        int k = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] != 0) {
                nums[k++] = nums[i];
            }
        }
        while(k < nums.length) {
            nums[k] = 0;
            k++;
        }
    }
}

总结： 思考时，不要太局限于题眼本身，还要学会反向思考，这应该也是出题人的目的。