这篇文章上次修改于 1207 天前，可能其部分内容已经发生变化，如有疑问可询问作者。 > 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 ##### 示例： ``` 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] ``` ##### 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数 ##### 解题思路1---暴力解法 1.遍历nums，碰到0，位置i，记录为第j个0， 2.如现在为第一个0 3.把i+1 和n-j-1 个元素前移 4.把第n-j个元素设置为0 5.继续从第i个位置查找0 ，重复1-4 6.直到i ==n-j,终止 ```java static void moveZeroes(int[] nums){ int j = 0; int i = 0; int n = nums.length; //寻找非0 while( i < n-j ){ if(nums[i] != 0){ i++; continue; } j++; //碰到0 ，前移 for(int k = i;k < n-j;k++){ nums[k] = nums[k+1]; } nums[n-j] =0; } } ``` * 这种解法为O(n^2)，肯定不是最优解 ##### 解题思路2---优化---类似冒泡思想 1.i,j=0,从第i个开始遍历数组，j表示前面j-1个都已经替换为非0了 2.1判断num[i]为非0，把num[i] 放入nums[j],j++，然后把nums[i]置为0 2.2这里要注意i==j的情况，表示第i个前面一直都是非0，不要把nums[i]置为0 3.遍历到结束 ``` java for (int i = 0, j = 0; i < nums.length; i++) { if (nums[i] != 0) { nums[j] =nums[i]; if(i != j){ nums[i]=0; } j++; } } ``` * 算法复杂度O(n) 附leetcode地址[https://leetcode-cn.com/problems/move-zeroes/](https://leetcode-cn.com/problems/move-zeroes/)
没有评论