题目描述
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
样例
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
输入: nums = [0]
输出: [0]
算法1
(双指针法) $O(n)$
设置快慢(双)指针,slow、fast,先以fast为工作坐标,
遍历一遍数组(while fast<len(nums)),让访问到的数值(nums【fast】)
不为0的赋值给slow坐标对应的单元(nums【slow】),并让slow坐标往后移一步(slow=slow+1),执行完一遍遍历后,最后再将slow往后的数赋值为0即可。
时间复杂度
O(n)
python 代码
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
slow,fast=0,0
while fast<len(nums):
if nums[fast]!=0:
nums[slow]=nums[fast]
slow=slow+1
fast=fast+1
while slow<len(nums):
nums[slow]=0
slow=slow+1
return nums
Java 代码
class Solution {
public void moveZeroes(int[] nums) {
int slow=0;
int fast=0;
while (fast<nums.length){
if (nums[fast]!=0){
nums[slow++]=nums[fast];
}
fast++;
}
while (slow<nums.length){
nums[slow++]=0;
}
}
}