LeetCode283.零移动

LeetCode283.零移动

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

示例:

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

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

思路1、先把所有非零依次排在数组前面，保持原有相对顺序，最后缺少的几位直接补0

void method1(int[] nums) {
        int length = nums.length;
        int insertIndex = 0;
        for (int i = 0; i < length; i++) {
            if (nums[i] != 0) {
                nums[insertIndex] = nums[i];
                insertIndex++;
            }
        }

        for (; insertIndex < length ; insertIndex++) {
            nums[insertIndex] = 0;
        }
    }

思路2、交换法

一个变量（指针）记录当前需要交换的0的索引
一个变量（指针）记录当前需要交换的非零数字的索引

void method2(int[] nums) {
        
        int length = nums.length;
        int zeroIndex = 0;
        int nonZeroIndex = 0;
        for (; nonZeroIndex < length; nonZeroIndex++) {
            if (nums[nonZeroIndex] != 0) {
                if (nonZeroIndex != zeroIndex) {
                    nums[zeroIndex] = nums[nonZeroIndex];
                    nums[nonZeroIndex] = 0;
                }
                zeroIndex++;
            }
        }
    }

滚雪球思维

遍历数组，将数组中的0当做雪，进行滚雪球，越滚越大，当遇到非零数字，就讲该数字和雪球中第一个位置进行交换
因此要记录雪球的大小
初始 [0,1,0,3,12]
第一步，第一个位置为0, 雪球大小为1，不做任何处理 [0,1,0,3,12]
第二步，数字为1，那么将1和雪球的第一个位置交换（或者就是将雪球第一个位置设置为1，数字1的位置置为0） [1,0,0,3,12]
第三步，数字为0，那么雪球变大了，大小为2， [1,0,0,3,12]
第四步， 数字为3，那么将3和雪球的第一个位置交换（或者就是将雪球第一个位置设置为3，数字3的位置置为0） [1,3,0,0,12]
第四步， 数字为12，那么将12和雪球的第一个位置交换（或者就是将雪球第一个位置设置为12，数字12的位置置为0） [1,3,12,0,0]

void method3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

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

            else if (snowBallSize > 0) {
                nums[i - snowBallSize] = nums[i];
                nums[i] = 0;
            }
        }

    }