题目描述
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-2^31 <= nums[i] <= 2^31 - 1
进阶:你能尽量减少完成的操作次数吗?
简单思路
使用双指针l,r。l为左到右第一个为0的下标,r为l右第一个不为0的下标。交换位置即可
代码
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
l = 0
r = 0
while(r<len(nums) and l <len(nums)):
while(l <len(nums) and nums[l]!=0):
# 找到为0的数的位置
l+=1
while(r<len(nums) and nums[r]==0):
# 找到l位置后不为0的数位置
r+=1
if(l > r):
r = l+1
elif(r < len(nums)):
temp = nums[r]
nums[r] = nums[l]
nums[l] = temp
l = l + 1
r = r+1
进阶思路
快慢指针实现,快慢指针均从数组开始往后走,快指针每次走一步,判断是否当然位置是0,不是时,把快指针的指向的值复制到慢指针所在位置,并且慢指针往后走一步.当快指针走完时,将慢指针后的所有值赋值为0.
代码
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
for i in range(slow, len(nums)):
nums[i] = 0