Leetcode 283：Move Zeroes

2023-11-02 10:05:28

Leetcode 283：Move Zeroes

Given an array nums, write a function to move all 0'sto the end of it while maintaining the relative order of the non-zero elements.

几个要点：

将 0 全部移动到数组后面
不打算非 0 元素的顺序

[法1] 暴力法

思路

① 新建一个相同大小的数组 result，数组初始化的时候所有元素本身就默认为 0；

② 遍历原数组 nums，将不为 0 的元素依次放入 result 中；

③ 复制 result 数组到 nums 数组

代码

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

        //临时数组
        int[] result = new int[nums.length];

        //临时数组索引
        int j = 0;

        //遍历原数组
        for(int i = 0;i < nums.length; i++){

            //找到非0的元素
            if(nums[i] != 0){
                //复制给临时数组 result
                result[j] = nums[i];
                //迭代 result 数组的索引
                j++;
            }
          
        }

        //复制 result 到 nums
        for(int i = 0;i<nums.length;i++){
            nums[i] = result[i];
        }
    }
}

提交结果

代码分析

时间复杂度：代码中只有一层循环（虽然有2次循环，不过不是嵌套的），很明显是 O(n)。
空间复杂度：我们使用了一个临时数组，所以空间复杂度是 O(n)。

改进思路

从在 Leetcode 上的提交结果可以看出我们当前算法比较大的问题就是内存消耗比较大，而我们内存消耗大的原因就是我们使用了一个临时数组，使得我们的空间复杂度为 O(n)，故而改进思路的方式就是想办法不借用临时数组，直接在原数组上操作。

[法2] 不用辅助空间

思路

仔细思考一下，其实这里辅助空间是完全没有必要的。

我们只需要在遇到非 0 元素的时候，直接把它赋值到前面就可以了。

而且由于非 0 元素的个数一定是小于或等于整个数组的元素个数的，所以在赋值到前面的时候，我们不用担心这个赋值会覆盖掉任何的数据。

整体思路如下：

① 遍历 nums，将非 0 元素复制到前面

② 把后面的元素全部置为 0

代码

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

        //非 0 元素的索引，[0...j) 的元素为非0元素
        int j = 0;

        //遍历原数组
        for(int i = 0;i < nums.length; i++){
            //找到非0的元素
            if(nums[i] != 0){
                //将非0元素移动到前面
                nums[j] = nums[i];
                //迭代索引
                j++;
            }
        }

        //后面全部置为0
        for(int i = j;i<nums.length;i++){
            nums[i] = 0;
        }
    }
}

提交结果

代码分析

时间复杂度：O(n)
空间复杂度：O(1)

改进思路

前面我们改进了空间复杂度。我们再看看代码的话会发现我们这里使用了 2 个步骤：复制非0元素和置0后面的元素。

一个改进思路就是：能不能在复制非0元素的同时将后面的元素置为0。

[法3] 一步到位

思路

要做到在复制非0元素的同时将后面的元素置为0，很明显思路就是：将非0元素和0元素进行交换。

整体思路如下：

① 建立 2 个索引，一个是非0元素索引j，一个是数组遍历索引 i

② 遍历到数组第 i 个元素后，保证 [0…i] 中所有非0元素都按顺序排列在 [0…j) 当中，同时要保证 [j…i] 为0

代码

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

        //nums 中[0....k)的元素为非0元素
        int j = 0;

        //遍历数组
        for(int i = 0;i < nums.length; i++){
            //找到非0的元素
            if(nums[i] != 0){
                //保证[0...i]中所有非0元素按顺序排列在[0...j)中
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                //迭代索引，保证 [j..i] 全为0
                j++;
            }
        }
    }
}

提交结果

代码分析

时间复杂度：O(n)
空间复杂度：O(1)

改进思路

当前代码我们是将非0元素和0元素进行交换，做到一步到位。但是就有一个问题了：非0元素经常会进行自己跟自己进行交换。举一个简单的例子就是所有元素都是非0的，那么这个情况就非常明显了，所以改进思路就是：避免自身交换。

[法4] 避免自身交换

思路

想一下什么情况会进行自身交换，其实就是当 i = j 的时候，这个时候程序“误”认为 [j…i] 都为0，所以进行了自身交换。因此我们只需要加一个判断：当 i ≠ j 的时候，才进行交换。

代码

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

        //nums 中[0....k)的元素为非0元素
        int j = 0;

        //遍历数组
        for(int i = 0;i < nums.length; i++){
            //找到非0的元素
            if(nums[i] != 0){
                if(i != j){
                    //保证[0...i]中所有非0元素按顺序排列在[0...j)中
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }
                //迭代索引，保证 [j..i] 全为0
                j++;
            }
        }
    }
}

码农公寓