本文共 2507 字，大约阅读时间需要 8 分钟。

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

示例:

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

说明:

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

解题思路

我们首先想到的做法是：遍历一遍数组nums，将非0元素添加到一个新建立的数组nonZeroElements中，然后将nonZeroElements中的元素copy到nums的最前面，对nums后面的元素赋值0即可。

class Solution:    def moveZeroes(self, nums):        """        :type nums: List[int]        :rtype: void Do not return anything, modify nums in-place instead.        """        nonZeroElements = []        for i in nums:            if i != 0:                nonZeroElements.append(i)        nonZeroElements_len = len(nonZeroElements)        for i in range(nonZeroElements_len):            nums[i] = nonZeroElements[i]        nums_len = len(nums)        for i in range(nonZeroElements_len, nums_len):            nums[i] = 0

那么我们稍微分析一下这个解法，我们发现这个解法中使用了一个额外的辅助空间，那么我们能不能不使用额外空间呢？Yes。

我们可以使用一个变量k记录位置，我们通过遍历nums数组，将不为0的元素依次复制到nums的前面，并且记录我们复制了多少个元素，对len(nums)-k的元素置0即可。

class Solution:    def moveZeroes(self, nums):        """        :type nums: List[int]        :rtype: void Do not return anything, modify nums in-place instead.        """        k = 0        for i in nums:            if i != 0:                nums[k] = i                k += 1        nums_len = len(nums)        for i in range(k, nums_len):            nums[i] = 0

通过上面的方法，我们将算法的空间复杂度降到了O(1)级别，而算法的时间复杂度依旧是O(n)级别。

当然我们这里有一个更pythonic的做法

class Solution:    def moveZeroes(self, nums):            """            :type nums: List[int]            :rtype: void Do not return anything, modify nums in-place instead.            """            for j in range(nums.count(0)):                nums.remove(0)                nums.append(0)

但是从效率上远不及前面的做法。

我们看到上面的做法都是对非0元素和0元素分开考虑，那们我们可不可以对这两种元素同时考虑呢？我们通过不断的交换非0元素和0元素之间的位置做到这一点。

class Solution:    def moveZeroes(self, nums):        """        :type nums: List[int]        :rtype: void Do not return anything, modify nums in-place instead.        """        k = 0        for i, num in enumerate(nums):            if num != 0:                nums[i], nums[k] = nums[k], nums[i]                k += 1

上面的代码比之前的简洁了不少，但是依然还有可优化的空间。如果我们的数组全部是非0元素的话，上面代码就会对所有非0元素自己交换一次。所有可以有如下改进：

class Solution:    def moveZeroes(self, nums):        """        :type nums: List[int]        :rtype: void Do not return anything, modify nums in-place instead.        """        k = 0        for i, num in enumerate(nums):            if num != 0:                if i != k:                    nums[i], nums[k] = nums[k], nums[i]                k += 1

实际上这里的思想是借鉴了。

该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/80475808 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！