LeetCode 学习：移动零

https://leetcode-cn.com/problems/move-zeroes/ 方法1：

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ zero_count = 0 for i in range(len(nums)): if nums[i] == 0: zero_count += 1 for i in range(zero_count): nums.remove(0) for i in range(zero_count): nums.append(0)

耗时太长，尝试减少循环：

方法2：

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ zero_count = 0 n = len(nums) for i in range(n): i = i - zero_count if nums[i] == 0: zero_count += 1 nums.remove(0) nums.append(0)

remove是$O(n)$，所以整体$O(n^2)$，但是也不能用pop，

方法3：采用冒泡法，将目标元素排到末尾，

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(len(nums)-1): for j in range(len(nums)-i-1): if nums[j]==0: nums[j],nums[j+1] = nums[j+1],nums[j]

耗时更长了。

---

师父反馈：这道题是数组，不能使用append和remove操作。 师父的解答：https://blog.csdn.net/herosunly/article/details/86635282

对比师父的答案，在冒泡排序的应用那里，自己的判断条件不全面，完整的交换条件是对于0和非0元素，把0元素放到后面。 自己的： if nums[j] == 0 : 交换。 师父的： if nums[j] == 0 and nums[j+1] != 0: 交换。 因此修改如下：

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(len(nums)-1): for j in range(len(nums)-i-1): if nums[j]==0 and nums[j+1] != 0: nums[j],nums[j+1] = nums[j+1],nums[j]

执行用时反而更大了，这是因为if条件多了一个判断吗？

使用排序类方法的时间复杂度总是$O(n^2)$，师父对此进行了优化。 方法：把数据分为两部分：非0段和0段。通过一次循环把非0段的值放入到正确的位置，同时也就可以得到非零元素的个数，然后把0段的也放到正确的位置就OK了。这样就实现了$O(n)$的时间复杂度。本质上它是基于插入排序的改进。

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ insert_not_zeros = 0 for i in range(len(nums)): if nums[i] != 0: nums[insert_not_zeros] = nums[i] insert_not_zeros += 1 #for i in range(insert_not_zeros+1,len(nums)): # 错误点：insert_not_zeros 作为索引和作为统计个数的时候，相差一位。 # 索引是从0~insert_not_zeros-1 for i in range(insert_not_zeros,len(nums)): nums[i] = 0 return nums

题解中给了一次遍历的答案：

class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ if not nums: return 0 # 两个指针i和j j = 0 for i in xrange(len(nums)): # 当前元素!=0，就把其交换到左边，等于0的交换到右边 if nums[i]: nums[j],nums[i] = nums[i],nums[j] j += 1 作者：wang_ni_ma 链接：https://leetcode-cn.com/problems/move-zeroes/solution/dong-hua-yan-shi-283yi-dong-ling-by-wang_ni_ma/

看完之后没有理解到为什么这样就可以？不会打乱原有的非0元素顺序吗？ 然后看到评论区：如果元素不为0，i,j跟着一起动。如果元素为零，j记录为零的下标。