#283 Move Zeros(Easy) 力扣

题干:

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

示例:

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

说明:

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

我的思路:

这道题是easy难度的题,并且题干简单清晰,条件也说的很明白,不能额外拷贝数组。

以下是我的解法,包含了最初的思路:

   /**
     * 287 移动零 <br/>
     * 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
     *
     * 示例:
     * 输入: [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * ------------------
     * 说明:
     * 必须在原数组上操作,不能拷贝额外的数组。
     * 尽量减少操作次数。
     * ------------------
     * 思路:
     * 遍历一次数组,对元素进行判断 如果该元素是0,则将其余元素 index+1 ,将该元素置为数组尾部
     *
     * 疑问:
     * 1. 需要继续明确条件,该数组本身是否是有序的?
     *
     * 2. 对数组进行索引的移动是否很消耗性能
     * -------------------
     * 边界条件:如果数组传入是空?
     *
     * @param nums 目标数组
     */
    public static void moveZeroes(int[] nums) {
        // 边界条件判断,如果数组为空,直接返回
        if (nums == null || nums.length == 0) {
            return;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            // 如果元素是0,则进入判断条件,找到该元素之后第一个非0的元素,将当前索引元素与非0元素交换
            if (nums[i] == 0) {
                // 如果下个元素不是0,则正常处理 直接交换就行了,将最后一位赋值为0
                if (nums[i + 1] != 0) {
                    // 核心操作:将该元素之后的元素向左移一位,将末尾元素置为0
                    for (int j = i; j < nums.length - 1; j++) {
                        nums[j] = nums[j + 1];
                    }
                    nums[nums.length - 1] = 0;
                } else {
                    // 如果下个元素还是0,则开始判断到下个非0元素之间的元素数量
                    int zeroElementNums = 1; // 元素为0的数量
                    // 从这开始循环 找出下一个非0元素的值,
                    for (int j = i + 1; j < nums.length-1; j++) {
                        if (j <= nums.length - 1 && nums[j] == 0) {
                            zeroElementNums++;
                        }else {
                            // 注意,这里需要跳出的是外层循环,否则会继续 for 循环,程序出错
                            break ;
                        }
                    }
                    if (i + zeroElementNums  <= nums.length - 1) {
                        int noneZeroElementIndex = i + zeroElementNums ;
                        // 将第一个非0元素赋值给当前为0的元素
                        nums[i] = nums[noneZeroElementIndex];
                        nums[noneZeroElementIndex] = 0;
                        // 将第一个非0元素之后的元素向前移动一位
                        for (int j = noneZeroElementIndex; j < nums.length - 1; j++) {
                            nums[j] = nums[j + 1];
                        }
                        // 末尾置为0
                        nums[nums.length - 1] = 0;
                    }
                }
            }
        }
    }

【可以看到,过程非常惨烈,对比非常残酷。我的冗长且做了很多额外的遍历操作,导致时间复杂度非常差,但是解题的思路还是要记录下来的。】

image-20200812024146942

优秀答案:

这个思路就很简单了,同时理解了之后觉得也很精妙:

先排除边界条件,然后从第一个元素开始遍历,将非0元素赋值给为0的元素,idx 数量即为非0元素数量。

第二次循环只需要将数组[length - idx] 个元素即为 0元素对应的索引处设置为0即可。

 public static void moveZeroes2(int[] nums) {
        // 边界排除
        if (nums == null || nums.length <= 1) {
            return;
        }
        int idx = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[idx++] = num;
            }
        }
        while (idx < nums.length) {
            nums[idx++] = 0;
        }
    }

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。