leetcode: explore-array-28 移动零
leetcode: explore-array-28 移动零
eetcode explore 初级算法第八题。原题链接：
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/28/
题目分析
原题内容如下：
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.题意拆解：
1、输入为一个列表，这个列表只包含数字。 2、将所有的 0 提前，而其他数字要维持原有的顺序。
注意事项： 1、原地修改（注意: in-place 这个单词，经常在题目中会看到），即不能申明其他 list 、dict 类型。 2、尽量少的移动次数（当然这个并不重要，因为并没有实际限制移动的复杂度，前提还是以实现为主）。
参考答案
在了解完题目意思后，其实题目的主要难点在于 in-place 以及需要维持原来非 0 数字的长度。很自然的一个思考方向就是遍历整个数组，问题在于怎么去移动数据并且使得它保持顺序。
其实这里我们可以换位思考，看上去题目是要求移动 0，但实际上在移动 0 的同时，也移动了非 0 的数字，并且对非0的数字显然要求更多，它需要维持原来的顺序。所以如果我们将题目换成：
将列表中的非0数按原来的顺序移到最末尾呢？
这个时候再去考虑遍历时的移动问题，我们从右到左遍历，比如先固定 nums[0]，如果 nums[1] 非0，则不动，如果 nums[1] 为0，则交换位置。这样一轮下来，nums[0] 最终停下来的位置即是最终的位置，依次类推，可以得到最终的结果。参考答案如下：
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
# 解题思路： 不为 0 的元素，从它的位置往前移动，直接找到一个不为0的整数后面一位即可，或者是第一位
if not nums:
return
for i in range(len(nums)):
if nums[i] == 0:
continue
for j in range(i - 1, -1, -1):
if nums[j] != 0:
break
nums[j + 1], nums[j] = nums[j], nums[j + 1]
if __name__ == "__main__":
s = Solution()
nums = [0,1,0,3,12]
s.moveZeroes(nums)
print(nums)当然除了这种思路外，我们还可以再换位思考下，重点还是在非0数字上，如果我们事先将非0数字全部提到最前面来，然后确定好非0数字的个数与0的个数，最终只需要去拼接一下数字是不是也能达到同样的效果呢？过程如下：
[0,1,0,3,12]
非0数个数 c = 0
按顺序遍历，当发现数字非0， nums[c] = cur_num
即：
[1,1,0,3,13] c = 1
[1,3,0,3,12] c = 2
[1,3,12,3,12] c = 3
最终结果：
[0] * (len(nums) - c) + nums[0:c]这里通过 0 数字可以被覆盖的思想来解决了移动问题，参考代码如下：
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
# 解题思路2： 遍历一次数组，将不为0的数字依次提到最前面，然后后面的位置补0
if not nums:
return
i = 0
for j in range(len(nums)):
if nums[j] == 0:
continue
nums[i] = nums[j]
i += 1
for j in range(i, len(nums)):
nums[j] = 0
if __name__ == "__main__":
s = Solution()
nums = [0,1,0,3,12]
s.moveZeroes(nums)
print(nums)复杂度分析
第一种方式，时间复杂度为 O(n^2)，空间复杂度为 O(1)。 第二种方式，时间复杂度为 O(n)，空间复杂度为 O(1)。
显然第二种方式要优于第一种。