题目

//////////

  1. 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
  2. 示例:
  3. 输入: [0,1,0,3,12]
  4. 输出: [1,3,12,0,0]
  5. 说明:
  6. 必须在原数组上操作，不能拷贝额外的数组。
  7. 尽量减少操作次数。
  8. 来源：力扣（LeetCode）
  9. 链接：https://leetcode-cn.com/problems/move-zeroes
  10. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

第一种解法

  1. class Solution:
  3.     def moveZeroes(nums):
  4.         """
  5.         One pass
  6.         N is the size of nums
  7.         Time complexity: O(N)
  8.         Space complexity: O(1) 
  9.         """
  10.         index = 0
  11.         for num in nums:
  12.             if num != 0:
  13.                 nums[index] = num
  14.                 index += 1
  15.         for i in range(index, len(nums)):  # [1, 3, 2, 45, 0, 45, 0, 0]
  16.             nums[i] = 0
  17.         return nums
  18.     print(moveZeroes([1,0,3,2,0,45,0,0]))
  1. 复杂度分析
  3.         使用了两个遍历,时间复杂度为O(N),使用了一个变量存储值,空间复杂度为O(1)
  5. 结构分析
  7.         双指针,分为非零区和零区,主要操作为替换,依赖索引值
  9.  理解的难点
  11.          替换的原理是什么? 为什么从index开始清洗数据而不是index + 1
  13.     为什么替换到最后还会余最后一个非零数，从而需要使用另外一个遍历实现数据清洗
  15. 流程
  17.         给一个默认值为零的变量.将其设置为零,它的左边是非零区,右边是零区
  19.     对列表中的元素遍历,当遇到的元素为非零数字时,将其值赋值给当前最大的index值,并且将其的值加一,也就是将index向右移动一位
  21.     如此循环,直到拿完所有的非零数字,由于填充非零区的方法是赋值,所以直到最后一个数字赋值给合适的索引值,这个数字还是存在于原位置
  23.     这就引出第二个操作,对定界的索引值之后的所有数字进行清洗,全部替换为零
  25.     最后向函数返回修改后的列表
  27.  数据结构
  29.          这部分知识是使用python实现数组,数组的特点是连续存储,每个元素的物理位置是连续的
  31.     索引,搜索,查询都严重依赖索引值,他们发时间复杂度都是O(N)

第二种解法

  1. # -*- codeing = utf-8 -*-
  2. # @Time : 2/27/2021 11:05 AM
  3. # @Autor : Caesar
  4. # @File : 283_solution1.py
  5. # @ Software : PyCharm
  7. class Solution:
  8.     def moveZeroes(nums):
  9.         index, count = 0, 0
  10.         while index < len(nums):
  11.             if nums[index] == 0:
  12.                 del nums[index]
  13.                 count += 1
  14.             else:
  15.                 index += 1
  16.         nums.extend([0]*count)
  17.         return nums
  18.     print(moveZeroes([1,2,3,0,10,0,10,0,0,9]))
  1. 复杂度分析:
  3.         时间复杂度: 未知  空间复杂度: O(1)
  5. 结构分析:
  6.         extend() 函数用于在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表）
  7.     核心思路是删除后填充,保持数目和元素的一致
  8.     使用遍历删除元素,不会改变元素之间的相对顺序
  9.     这里仍然需要一个个指针,用于控制遍历的次数,究竟遍历到哪一个元素
  10.     一个计数器,专门统计零元素的个数,便于删除之后按照原本数目恢复元素
  11. 流程分析:
  13.         指定两个默认值为0的变量,一个用于计数,一个用于自增减,手动控制遍历
  14.     while循环,直到所有的元素都被if语句功能检查一遍,检查并且删除值为零的元素
  15.     如果值不为零,则不删除,但是计数器加一,继续进行对下一个元素的检查
  16.     然后,遍历完成所有元素,使用列表的extend方法,在列表末尾追加值为零的元素
  17.     最后向函数返回修改后的列表
  19. 我的收获
  21.         对元素的遍历,可以使用变量的自增减实现，除此之外，还可以使用循环，enumerate内置函数

第三种

  1. # -*- codeing = utf-8 -*-
  2. # @Time : 2/27/2021 6:21 PM
  3. # @Autor : Caesar
  4. # @File : 283_solution2.py
  5. # @ Software : PyCharm
  8. class Solution:
  9.     def moveZeroes(nums):
  10.         """
  11.         Do not return anything, modify nums in-place instead.
  12.         """
  13.         i = -1
  14.         for j in range(len(nums)):
  15.             if nums[j]!=0:
  16.                 i+=1
  17.                 nums[i],nums[j]= nums[j], nums[i]
  18.         return nums
  19.     print(moveZeroes([1,2,3,0,3,21,33,0,45]))
  20. '''
  21. 作者：xueliangwang
  22. 链接：https://leetcode-cn.com/problems/move-zeroes/solution/shuang-zhi-zhen-xiang-xi-tu-jie-by-xueliangwang/
  23. 来源：力扣（LeetCode）
  24. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  25. '''
  1. 复杂度分析：
  3.     时间复杂度： 遍历 O(N)  空间复杂度 ： O(1）
  5. 结构分析：
  6.         双指针，一个指针对有序区定界，一个指针负责遍历
  8.     有序区的范围都是遇零截断，那么最终的长度就是除去零以外所有元素的个数
  10.     这里的替换是一种对换，有序区的每一个数字都会和无需区的数字进行对换，零会从有序区对换出去