[LeetCode 笔记] 283. Move Zeroes

前言

　　这题题目要设法将阵列中的非零元素全部往前移，题目要求不能配置新的空间，所以不能使用辅助的 Array，那我们就由本身的阵列来做循环添加，这是比较简单的方法，需用到一层迴圈，时间複杂度推估可达 O(n)，这里有 JAVA 和 Python 的写法。

题目

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.

给定一个整数阵列为 nums，移动全部的 零 元素到最后面， 同时维持 非零 元素的原本顺序。
注意 你必须在当前阵列做，不能複製一个阵列来做。

题目连结：https://leetcode.com/problems/move-zeroes/

题目限制

1 <= nums.length <= 104
231 <= nums[i] <= 231 - 1
Follow up: Could you minimize the total number of operations done?

範例

Input: nums = [0,1,0,3,12]Output: [1,3,12,0,0]

Input: nums = [0]Output: [0]

思路&笔记

题目要求不能配置新的空间，所以不能用辅助的 Array，那我们就由本身阵列来做循环添加。

把非零元素加到当前阵列里从阵列的最前面开始添加，索引从 0 开始 (从阵列的最前面)再把当前的阵列后面补 0 即可，索引从 3 开始 (从刚添加完非零元素后面开始)

JAVA 实现

class Solution {    public void moveZeroes(int[] nums) {        if (nums == null || nums.length == 0) return; // 防止这个函式会直接回传传入的 nums 参数        int insert = 0;        // 把非零元素加到当前阵列里        for (int num: nums){            if (num != 0){                nums[insert++] = num; // 从阵列的最前面开始添加 (注意：元素会先被添加在 nums[insert]里，之后 insert 才会被 ++)            }        }        // 再把当前的阵列后面补 0 即可，索引从 3 开始        while (insert < nums.length){            nums[insert++] = 0; // 添加 0 进去        }    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def moveZeroes(self, nums: List[int]) -> None:                # 把非零元素加到当前阵列里        for i in range(len(nums)):            if nums[i] !=0: # 不是非 0 元素                nums[pointer] = nums[i]  # 取得当下元素，放到指定索引里                pointer += 1 # 索引++        # 再把当前的阵列后面补 0 即可，索引从 3 开始        for i in range(pointer, len(nums)):            nums[pointer] = 0 # 添加 0 进去            pointer += 1 # 索引 ++

Python 进阶实现

笔者还在学习中，参考了在讨论区里网友讨论度很高的 Swap 变数互换 简洁的算法。

把阵列中前面的元素和后面的元素设定好条件 (必须前面为非零元素，后面为零元素)将两个元素做交换，把非零元素换到前面最后后面索引 +1，进行下一次比较交换元素

class Solution:    def moveZeroes(self, nums: list) -> None:        slow = 0         for fast in range(len(nums)):            if nums[fast] != 0 and nums[slow] == 0: # 前面的元素、后面的元素                nums[slow], nums[fast] = nums[fast], nums[slow] # 将两个元素做交换            # 第一次循环，刚开始索引 fast[0] slow[0]            if nums[slow] != 0:                 slow += 1 # 索引 +1 后，换比较交换 fast[1] ，slow[2]

其他算法

双指针算法：https://medium.com/@urdreamliu/283-图解-move-zeroes-4da4900f5aac

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/05/05/LeetCode-283-Move-Zeroes-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论