给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序
注意事项
1.必须在原数组上操作
2.最小化操作数
样例
给出 nums = [0, 1, 0, 3, 12], 调用函数之后, nums = [1, 3, 12, 0, 0].
知识点
相向，同向型两根指针一直往前走，时间复杂度都为 O(n)，若左指针前进一步右指针回到初始位置重新走的话时间复杂度为 O(n^2),两根指针一般用在 O(n) 的时间复杂度，要比 O(nlogn) 快
思路
用同向型指针，一个指向第一个为 0 的元素，一个指向第一个不为 0 的元素， 在向右移动过程中不断把 0 交换到数组的末尾
代码
- 统计数组中 0 的个数，把不为 0 的数按照顺序全部加入到动态数组中，然后在按照统计个数把 0 加入，最后用数组复制下动态数组中的元素，时间复杂度 O(n) 空间复杂度 O(n)
public class Solution {
/*
* @param nums: an integer array
* @return:
*/
public void moveZeroes(int[] nums) {
int count = 0;
ArrayList<Integer> array = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
array.add(nums[i]);
} else {
count++;
}
}
while (count-- != 0) {
array.add(0);
}
for (int i = 0; i < nums.length; i++) {
nums[i] = array.get(i);
}
}
}
- 遍历过程中直接把非 0 数全拷贝到 nums 数组中，后面空位全部补 0，时间复杂度 O(N)，空间复杂度 O(1)
不存在非 0 数被覆盖的情形，0 被覆盖，非 0 数停留在原地
public class Solution {
/*
* @param nums: an integer array
* @return:
*/
public void moveZeroes(int[] nums) {
int lastNoZeroIndex = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[lastNoZeroIndex++] = nums[i];
}
}
for (int i = lastNoZeroIndex; i < nums.length; i++) {
nums[i] = 0;
}
}
}
- 上一种的时间复杂度在遍历完一遍数组后又遍历了 0 的个数，用两根指针优化时间复杂度，让算法只遍历一遍数组，时间复杂度 O(N)，空间复杂度 O(1)
AAA000BC ————> AAAB000C
left 始终指向第一个0只是下标在移动，right 刚开始指向 B，交换完后后移一位指向 C，始终是指向第一个非 0 数
public class Solution {
/*
* @param nums: an integer array
* @return:
*/
public void moveZeroes(int[] nums) {
// left 代表数组中第一个值为 0 的下标
// right 代表数组中第一个值不为 0 的下标
int left = 0, right;
for (right = 0; right < nums.length; right++) {
if (nums[right] != 0) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
/* 在没遇到第一个 0 之前，right 每移动一次 left 也跟着移动，
* left 和 right 始终指向同一元素，交换也是自己和自己的交换，
* 所以不会出现如果数组第一个元素不是 0，right++跑到 0，
* 而 left 仍在数组第一个元素处不动的反向交换情形
*/
left++;
}
}
}
}
