难度: Easy
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]
输出:[1,3,12,0,0]
示例 2:
输入: nums =[0]
输出:[0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶:你能尽量减少完成的操作次数吗?
难度: Easy
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]
输出:[1,3,12,0,0]
示例 2:
输入: nums =[0]
输出:[0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶:你能尽量减少完成的操作次数吗?
运行时间: 36 ms
内存: 17.0 MB
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ p1 = 0 for i in range(len(nums)): if nums[i]: nums[p1] = nums[i] p1+=1 for i in range(p1,len(nums)): nums[i]=0
本题解采用双指针的方法。初始时,两个指针都指向数组的开始位置。遍历数组,每当遇到非零元素时,就将该元素移动到第一个指针的位置,并将第一个指针向后移动一位。这样可以保证第一个指针之前的所有元素都是非零的。遍历完成后,将第一个指针及其之后的所有位置都填充为0,从而实现将所有0移动到数组末尾的目标。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution: def moveZeroes(self, nums: List[int]) -> None: # 初始化第一个指针 p1 = 0 # 遍历数组,将非零元素移动到数组前面 for i in range(len(nums)): if nums[i]: nums[p1] = nums[i] p1 += 1 # 将剩余位置填充为0 for i in range(p1, len(nums)): nums[i] = 0
在双指针方法中,选择将非零元素前移而不是直接交换位置的原因是为了保持非零元素的原始顺序。如果直接交换位置,那么非零元素的相对顺序可能会被打乱。此外,前移操作通常比交换操作更高效,因为交换涉及更多的写操作。
在第一次遍历的同时填充0是可能的。在移动非零元素时,可以立即将遍历到的位置设置为0,然后当移动到下一个非零元素时,再将其赋给前面的0位置。这样,第一次遍历完成后,数组后端自然填充了需要的0,从而减少了操作次数。但这需要确保不会覆盖还未处理的非零元素,可能需要增加条件判断来确保正确性。
为了确保在移动非零元素时不覆盖尚未处理的元素,可以使用一个辅助指针(p1)。这个指针仅在确定一个元素为非零并需要被移动时才前移。通过这种方式,我们只在发现非零元素时才将其移动到p1指向的位置,并立即将p1移动到下一个位置,这样可以确保不会误操作尚未遍历到的元素。
在数组全为0的情况下,该算法的性能表现良好。第一次遍历中,指针p1不会移动,因为没有非零元素。第二次遍历仅仅是重新确认填充0,实际上是多余的。在这种特定情况下,算法的时间复杂度仍为O(n),无需额外优化。这是因为即使优化掉第二次遍历,整体性能提升不大。