你不可不会的几种移动零的方法（续集）

原创

程序员小熊

修改于 2021-06-26 13:12:13

4100

修改于 2021-06-26 13:12:13

文章被收录于专栏：程序员小熊带你学算法程序员小熊带你学算法

前言

大家好，我是「程序员小熊」，就职于「华为」。在上期你不可不会的几种移动零的方法中，小熊主要介绍了「末尾补零」和「交换零元素与非零元素」两种方法解答力扣第283题-移动零。

本文提供采用「双指针」策略的「覆盖法」来解决这道题，供大家参考，希望对大家有所帮助。

移动零

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


示例:

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

说明:

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

解题思路

根据题意，要把数组中所有 0 移动到数组的末尾，还要保持非零元素的「相对位置」，可以通过设置两个指针（i 和 j），其中 i 用于遍历整个数组，j 用于依次保存 i 在遍历时遇到的非零元素，当 j 保存完 i 在遍历完数组中的非零元素之后，将原剩余的元素全部用零替换即可。

覆盖法

「举例」

以数组 nums =[0,1,0,3,12]为例子，如下图示。

遍历整个数组，并将遍历到的非零元素保存。

遍历和保存（依次）非零元素的完整过程，如下动图示。

Show me the Code

「C」

void moveZeroes(int* nums, int numsSize){
    int i = 0, j = 0;
    while (i < numsSize) {
        /* 遍历找出数组中的非零元素 */
        if (nums[i] != 0) {
            /* 保存遍历到的非零元素 */
            if (i != j) {
                /* 数组全为非零元素，不需要保存 */
                nums[j] = nums[i];
            }
            j++;
        }
        i++; 
    }

    while (j < numsSize) {
        nums[j++] = 0;
    }
}

「C++」

void moveZeroes(vector<int>& nums) {
    int i = 0, j = 0;
    int len = nums.size();
    while (i < len) {
        if (nums[i] != 0) {
            if (i != j) {
                nums[j] = nums[i];
            }
            j++;
        }
        i++; 
    }

    while (j < len) {
        nums[j++] = 0;
    }
}

「Java」

void moveZeroes(int[] nums) {
    int i = 0, j = 0;
    int len = nums.length;
    while (i < len) {
        if (nums[i] != 0) {
            if (i != j) {
                nums[j] = nums[i];
            }
            j++;
        }
        i++; 
    }

    while (j < len) {
        nums[j++] = 0;
    }
}

「Python3」

def moveZeroes(self, nums: List[int]) -> None:
    i, j = 0, 0
    length = len(nums)
    while i < length:
        if nums[i] != 0:
            if i != j:
                nums[j] = nums[i]
            j += 1
        i += 1

    while j < length:
        nums[j] = 0
        j += 1

「Golang」

func moveZeroes(nums []int)  {
    j, length := 0, len(nums)
    for i := 0; i < length; i++ {
        if nums[i] != 0 {
            if i != j {
                nums[j] = nums[i]
            }
            j++
        }
    }

    for j < length {
        nums[j] = 0
        j++
    }
}

「复杂度分析」

时间复杂度：「O(n)」，其中 n 是数组的长度，需要遍历一遍数组。

空间复杂度：「O(1)」，未开辟额外的存储空间。

「说明」

代码中加「i 是否等于 k」的判断，为了避免当数组中的所有元素都是「非零元素」，再去保存非零元素，也算一个小的优化。