力扣283.移动零

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

思路一：

快慢指针遍历数组，把第0个非零数字移动到nums[0], 第一个非零数字移动到nums[1]，第i个非零数字移动到nums[i]的位置

 1 class Solution {
 2     public void moveZeroes(int[] nums) {
 3         if(nums == null){
 4             return;
 5         }
 6 
 7         int noneZeroIndex = 0;
 8         int n = nums.length;
 9         for(int i = 0; i < n; i++){
10             if(nums[i] != 0){
11                 nums[noneZeroIndex++] = nums[i];
12             }
13         }
14         // 把noneZeroIndex部分的所有元素都置为0
15         Arrays.fill(nums, noneZeroIndex, n, 0);
16     }
17 }

力扣测试时间为0ms, 空间为40.2MB

复杂度分析：

时间复杂度为O(n)

空间复杂度为O(1)

思路二：

对上面的解法做了一点小改进，在判断nums[i]非零时，交换nums[i]和nums[noneZeroIndex]两个元素，而非仅仅给nums[noneZeroIndex]赋值，这样可以去除第二轮迭代。之所以选择交换而非直接给nums[i]赋值为0，是因为，如果刚好i == noneZeroIndex, 那么将引发错误。

 1 class Solution {
 2     public void moveZeroes(int[] nums) {
 3         if(nums == null){
 4             return;
 5         }
 6 
 7         int noneZeroIndex = 0;
 8         int n = nums.length;
 9         for(int i = 0; i < n; i++){
10             if(nums[i] != 0){
11                 int temp = nums[noneZeroIndex]; // 交换noneZeroIndex和i的元素
12                 nums[noneZeroIndex++] = nums[i];
13                 nums[i] = temp;
14             }
15         }
16     }
17 }

力扣测试时间为：0ms，空间为：39.9MB

复杂度分析：

时间复杂度为O(n)

空间复杂度为O(1)

思路三：

同样是快慢指针
遍历数组，把当前0与下一个非0元素进行交换

 1 class Solution {
 2     public void moveZeroes(int[] nums) {
 3         if(nums == null){
 4             return;
 5         }
 6 
 7         // 遍历数组，把当前0与下一个非0元素进行交换
 8         int n = nums.length;
 9         int j= 0;
10         for(int i = 0; i < n; i++){
11             if(nums[i] == 0){
12                 for(j = j + 1; j < n && nums[j] == 0; j++); // 查找下一个不为0的数字
13                 if(j < n){  // 如果j < n, 交换nums[i] 和nums[j]
14                     nums[i] = nums[j];
15                     nums[j] = 0;
16                 }else{
17                     break;  // 如果j >= n，说明0已经全被移动到了末尾
18                 }
19             }else{
20                 j++;
21             }
22 
23         }
24     }
25 }

力扣测试时间为0ms, 空间为：39.8MB

复杂度分析：

时间复杂度：i和j指针都只遍历了一次数组，所以时间复杂度为O(n),

空间复杂度: 为O(1)

思路参考：

https://leetcode-cn.com/problems/move-zeroes/solution/yi-dong-ling-by-leetcode/