移动零
给定一个数组
nums
,编写一个函数将所有0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
1、双指针
class Solution {
public void moveZeroes(int[] nums) {
//...省略判空
for (int p = 0, i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[p];
nums[p++] = temp;
}
}
}
}
不考虑数组为空或者长度为0为1的情况,多加一个if而已。
开始时两个指针都指向第1个元素,然后判断当前值是否为0,如果是0,则 p 指针维持原位置不动,i 指针向后移动一位,当 i 指针指向的元素不为0的时候,
则将其与p指针的下一个元素交换(此时 p 指针的下一个元素一定是0),同时 p 指针向后移动一位。
重复此过程直至到最后一位,
2、标记后统一清零
class Solution {
public void moveZeroes(int[] nums) {
//...省略判空
int index = 0;
for(int num:nums){
if(num!=0){
nums[index++]=num;
}
}
while(index<nums.length){
nums[index++] = 0;
}
}
}
这个方法相当于把当前数组整个重新构造了一遍。
可以看作是从前往后数,有一个分界线,此分界之前全不为0,分界之后全为0。
遍历数组,只要当前数不为零,就将此值依次放到分界线之前的位置上。
放完之后,不管后面还剩几个位置,全部置为0即可。