【数据结构和算法】移动零

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

---

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一：双指针

2.2 方法二：两次遍历

2.3 方法三：一次遍历

三、代码

3.1 方法一：双指针

3.2 方法二：两次遍历

3.3 方法三：一次遍历

四、复杂度分析

4.1 方法一：双指针

4.2 方法二：两次遍历

4.3 方法三：一次遍历

---

前言

这是力扣的283题，难度为简单，解题方案有很多种，本文讲解我认为最奇妙的三种。

---

一、题目描述

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

请注意?，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums =[0,1,0,3,12]

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

示例 2:

输入: nums = [0]

输出: [0]

提示:

• 1 <= nums.length <= 104
• -231?<= nums[i] <= 231?- 1

进阶：你能尽量减少完成的操作次数吗？

---

二、题解

2.1 方法一：双指针

思路与算法：

使用双指针，i 指针指向当前已经处理好的序列的尾部，j 指针指向待处理序列的头部。

j 指针不断向右移动，每次 j 指针指向非零数，则将 i j 指针对应的数交换，同时 i 指针右移。

注意到以下性质：

1. i 指针左边均为非零数；
2. j 指针左边直到左指针处均为零。

因此每次交换，都是将 i 指针的零与 j 指针的非零数交换，且非零数的相对顺序并未改变。

2.2 方法二：两次遍历

思路与算法：

首先创建两个指针 i 和 j，第一次遍历的时候指针 j 用来记录当前有多少非 0 元素。

即遍历的时候每遇到一个非 0 元素就将其往数组左边挪，第一次遍历完后，j 指针的下标就指向了最后一个非 0 元素下标。

第二次遍历的时候，起始位置就从 j 开始到结束，将剩下的这段区域内的元素全部置为 0。

2.3 方法三：一次遍历

思路与算法：

参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点 x，然后把所有小于等于 x 的元素放到 x 的左边，大于 x 的元素放到其右边。

这里我们可以用 0 当做这个中间点，把不等于 0(注意题目没说不能有负数)的放到中间点的左边，等于 0 的放到其右边。

这的中间点就是 0 本身，所以实现起来比快速排序简单很多，我们使用两个指针 i 和 j，只要 nums[i]!=0，我们就交换 nums[i] 和 nums[j]

---

三、代码

3.1 方法一：双指针

Java版本：

class Solution {
    public static void moveZeroes(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) return;
        int i = 0, j = 0;
        while (j < n) {
            if (nums[j] != 0) {
                reserve(nums, i, j);
                i++;
            }
            j++;
        }
    }

    void reserve(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

C++版本：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), i = 0, j = 0;
        while (j < n) {
            if (nums[j]) {
                swap(nums[i], nums[j]);
                i++;
            }
            j++;
        }
    }
};

3.2 方法二：两次遍历

Java版本：

class Solution {
    public static void moveZeroes1(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) return;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (int i = j; i < n; i++) {
            nums[i] = 0;
        }
    }
}

C++版本：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        if (n == 0 || n == 1) return;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (int i = j; i < n; i++) {
            nums[i] = 0;
        }
    }
};

3.3 方法三：一次遍历

Java版本：

class Solution {
   public static void moveZeroes2(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) return;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j++] = temp;
            }
        }
    }
}

C++版本：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        if (n == 0 || n == 1) return;
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j++] = temp;
            }
        }
    }
};

---

四、复杂度分析

4.1 方法一：双指针

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

4.2 方法二：两次遍历

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

4.3 方法三：一次遍历

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

---