283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0] 输出: [0]
提示:
进阶： 你能尽量减少完成的操作次数吗？
解法一
思路分析：
- 题目要求保持非零元素的相对顺序的情况下，将所有0都移动到数组末尾，那么我们考虑使用快慢双指针法，使用快指针遍历需要移动的元素，使用慢指针指向0所在位置。
- 在完成题目要求时，我们还需要考虑如何使交换元素发生次数最少。
实现代码如下：
java
class Solution {
public void moveZeroes(int[] nums) {
if (nums.length == 1)
return ; // 数组长度为1时不需要移动
int fast;
int slow = 0;
// 记录数组元素不为0的数量 用于从数组后端重新将0赋值
// 避免反复覆盖nums[fast] 快指针指向的值
int count = 0;
// 循环寻找第一个不为0的索引 避免数组前端不为0的元素重复赋值
while (slow < nums.length && nums[slow] != 0) {
++ slow;
++ count;
}
// 说明数组中不含有为0的元素 不需要移动数组元素
if (slow == nums.length) {
return ;
}
// 慢指针指向的数组元素为0的索引处 快指针从下一个索引开始搜索不为0的数组元素
fast = slow+1;
while(fast < nums.length) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
count++;
}
++ fast;
}
if (count == 0) { // 说明数组元素全为0 不需要移动
return ;
}
count = nums.length-count;
// 将0赋值给数组末尾
for (int i = nums.length-1; i >= 0 && count > 0; -- i, -- count) {
nums[i] = 0;
}
}
}提交结果如下：
text
解答成功:
执行耗时:1 ms,击败了99.97% 的Java用户
内存消耗:43.8 MB,击败了82.25% 的Java用户复杂度分析：
- 时间复杂度：O(n+m)，n是数组长度，m是为数组中元素为0的个数
- 空间复杂度：O(1)
考虑程序执行过程，slow-1最后指向了数组移动后，最后一个不为0的数组元素位置，因此不需要再使用count来统计不为0的数组元素个数，slow本身已经实现了统计数组元素个数的过程；优化代码如下所示：
java
class Solution {
public void moveZeroes(int[] nums) {
if (nums.length == 1)
return ; // 数组长度为1时不需要移动
int fast;
int slow = 0; // 遍历保存非0数组元素 并统计非0元素个数
// 循环寻找第一个不为0的索引 避免数组前端不为0的元素重复赋值
while (slow < nums.length && nums[slow] != 0) {
++ slow;
}
// 说明数组中不含有为0的元素 不需要移动数组元素 直接返回
if (slow == nums.length) {
return ;
}
// 慢指针指向数组元素为0的索引处
// 快指针从下一个索引开始搜索不为0的数组元素
fast = slow+1;
while(fast < nums.length) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
}
++ fast;
}
// 进行移动后 若 slow==0 则说明数组元素均为0 不需要再进行重赋值为0
if (slow == 0) return ;
// 进行重赋值为0
while (slow < nums.length)
nums[slow ++] = 0;
}
}提交结果如下：
text
解答成功:
执行耗时:1 ms,击败了99.97% 的Java用户
内存消耗:44.4 MB,击败了5.03% 的Java用户