数组-283移动零-简单-20210723

1. 题目描述

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

示例：

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

说明：

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

尽量减少操作次数

2. 题目解答

2.1 第一次尝试答案

伪代码：for 遍历：元素为0，删除，数组末尾加0

缺点：时间复杂度N^2/首先应该排除空数组

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in nums:
            if i == 0:
                nums.remove(i)
                nums.append(0)

2.2 官方题解

思路及解法

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

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

注意到以下性质：

• 左指针左边均为非零数；

• 右指针左边直到左指针处均为零。

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

• 时间复杂度：O(n)，其中 n为序列长度。每个位置至多被遍历两次。
• 空间复杂度：O(1)，只需要常数的空间存放若干变量。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

2.3 评论较优解答

• 每个索引为非零元素，排满后补零
• 时间复杂度：O(2n)，空间复杂度：O(1)

class Solution(object):
    def moveZeroes(self, nums):
        index = 0
        for num in nums:
            if num != 0:
                nums[index] = num
                index += 1
         for i in range(index, len(nums)):
            nums[i] = 0

3. 错解

无