283. 移动零

暴力解法

class Solution {
    public void moveZeroes(int[] nums) {

        /**
         * 使用额外的数组存放非零元素
         */
        int[] temp = new int[nums.length];
        int index = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != 0){
                temp[index++] = nums[i];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

优化1——双指针法

class Solution {
    public void moveZeroes(int[] nums) {

        /**
         * 不使用额外的空间，n指向左边非零子数组的后一位，i指向当前遍历元素
         * 记录最后一个非零元素的位置
         */
        int n = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != 0){

                nums[n] = nums[i];
                n++;
            }
        }

        for (int i = n; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化2——不单独赋值后面的元素为零

class Solution {
    public void moveZeroes(int[] nums) {

        /**
         * 每当遇到一个非零元素，就和第n个元素互换位置，n初始为0
         * 这样所有的非零元素都会按顺序在前面，0全部被换到了后面
         */
        int n = 0;
        int temp = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != 0){

                temp = nums[i];
                nums[i] = nums[n];
                nums[n] = temp;
                n++;
            }
        }
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化3——减少交换元素的次数

class Solution {
    public void moveZeroes(int[] nums) {

        /**
         * 每当遇到一个非零元素，就和第n个元素互换位置，n初始为0
         * 这样所有的非零元素都会按顺序在前面，0全部被换到了后面
         */
        int n = 0;
        int temp = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != 0){

                /**
                 * 如果数组都是非零元素，那么每次都会和自己交换
                 * 因此判断一下是否真的需要交换
                 */
                if (i != n) {
                    temp = nums[i];
                    nums[i] = nums[n];
                    nums[n] = temp;
                }

                n++;
            }
        }
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

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