给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入:[0,1,0,3,12]
输出:[1,3,12,0,0]
说明:
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
比较暴力的做法,就是依次判断是否为0,如果是0,用后面的数循环盖掉前面的数,然后在最末尾补0。就这样直到循环结束。不过这里要注意到循环结束的条件,未处理的数组内容是在缩短的,处理过的内容(也就是放在末尾的0)不需要重新处理。
代码如下:
1 class Solution { 2 public void moveZeroes(int[] nums) { 3 int len=nums.length; 4 for(int i=0;i<len;i++) 5 { 6 if(nums[i]==0) 7 { 8 for(int j=i;j<nums.length-1;j++) 9 { 10 nums[j]=nums[j+1]; 11 } 12 nums[nums.length-1]=0; 13 i--; 14 len--; 15 } 16 } 17 } 18 }
同时网友题解也给出了比较聪明的做法。就是快慢指针。快针遍历,遇到非0,就让慢针指向的位置置为那个值,如果是0,则跳过。最后把缺的地方补全0。这样减少了数组本身的移动次数,有效提高了代码执行效率
代码如下:
1 class Solution { 2 public void moveZeroes(int[] nums) { 3 int i=0,j=0; 4 for(;i<nums.length;i++) 5 { 6 if(nums[i]!=0) 7 nums[j++]=nums[i]; 8 9 } 10 while(j<nums.length) 11 nums[j++]=0; 12 } 13 }