【算法题解】59. 移动零

❝

这是一道 「简单」 题
https://leetcode.cn/problems/move-zeroes/

❞

题目

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

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

示例 1:

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

示例 2:

输入: nums = [0] 
输出: [0]

提示:

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

题解

本题可以使用「双指针」的解法。

分别定义两个指针 和 ，下标都是从 开始。

使用指针 遍历数组中的每一个元素，使用指针 依次记录遇到的不为 的元素：

1. nums[i] != 0: 可以记录，即 ，同时将  向后移动一步。
2. nums[i] == 0: 不做记录， 的位置保持不变。

以示例一 为例，动图中绿色表示记录移动后的值，蓝色表示遍历过的值。

答案是不会的，因为指针 肯定是指针 慢的，所有指针 遇到的非 值在前面已经记录过了，所以可以放心大胆的覆盖。

Java 代码实现

class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        for(int i = j; i < nums.length; i++){
            nums[i] = 0;
        }
    }
}

Go 代码实现

func moveZeroes(nums []int)  {

    n := len(nums)

    j := 0

    for i := 0; i < n; i++ {
        if nums[i] != 0 {
            nums[j] = nums[i]
            j++
        }
    }

    for i := j; i < n; i++ {
        nums[i] = 0
    }

}

复杂度分析

时间复杂度：, N 为数组 nums 的长度。

空间复杂度：。

– End –

如果觉得有所收获，就顺道点个关注吧！