LeetCode 283. 移动零 Move Zeroes

2023-01-07 100

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode 283. 移动零 Move Zeroes

LeetCode 283. 移动零 Move Zeroes

Table of Contents

一、中文版

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

示例:

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

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

说明:

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。

二、英文版

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

三、My answer

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        j = 0
        while j != len(nums):
            if nums[i] == 0:
                if nums[j] != 0:
                    # 初级写法
                    # temp = nums[i]
                    # nums[i] = nums[j]
                    # nums[j] = temp
                    # 优雅写法
                    nums[i],nums[j] = nums[j],nums[i]
                    i += 1
                else:
                    j += 1
            else:
                i += 1
                j += 1

四、解题报告

算法：同向双指针，j 是快指针，i 是慢指针，所以 j 会先到结尾。

分为 nums[i] =0 和 != 0 两种情况， != 0 时两个指针就继续向后移动。

i = 0 时，需要跟后边的元素交换才能把 0 换到后面。此时后续操作跟 nums[j] 相关，如果 nums[j] == 0，则 j 向后移动，直到nums[j] 不等于0；否则执行交换操作。Python 交换有个简便写法：nums[i],nums[j] = nums[j],nums[i]

LeetCode 283. 移动零 Move Zeroes