算法随笔_31:移动零
上一篇:算法随笔_30: 去除重复字母-CSDN博客
=====
题目描述如下:
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]
=====
算法思路:
题目要求原地对数组进行操作。我们可以设两个下标指针p1，p2，p1=0，p2=0。
然后从左往右枚举数组，先不断移动p2，如果p2处不为0，我们把p1的元素和p2所指元素交换，然后继续移动p1。如果p2处为0，我们继续移动p2。
以此类推，直到p2到达数组末尾。此时的数组已经符合题目要求。
class Solution(object):
def moveZeroes(self, nums):
p1=0
p2=0
nums_len=len(nums)
while p2<nums_len:
if nums[p2]!=0:
nums[p1],nums[p2]=nums[p2],nums[p1]
p1+=1
p2+=1
此算法的时间复杂度为O(n) 。