283. 移动零-双指针(易)
题目描述
链接: https://leetcode-cn.com/problems/move-zeroes/submissions/
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
1必须在原数组上操作,不能拷贝额外的数组。
2尽量减少操作次数。
解题思路
这道题我们直接用双指针的快慢指针进行遍历即可.
慢指针指向要被替换的下标, 快指针遍历整个列表.
注意: 不能替换后直接nums[fast] = 0, 这样当快慢指针指向同一元素且为非0(不用动)时,根据代码会变成0.
复杂度分析
T: O(n)
S: O(1)
代码
class Solution { public void moveZeroes(int[] nums) { int fast = 0, slow = 0; while (fast < nums.length) { if (nums[fast] == 0) { fast++; } else { //解法1: 不进行交换, 进行覆盖, 则需要循环结束后把剩余部分置0 //解法2: 进行交换(fast与slow交换, 则不需要再置0). nums[slow] = nums[fast]; slow++; fast++; } } while (slow < nums.length) { nums[slow] = 0; slow++; } } }