LeetCode.283.Move Zeroes 将数组中的零移到末尾

题目描述

283 Move Zeroes
https://leetcode-cn.com/problems/move-zeroes/
https://leetcode.com/problems/move-zeroes/description/

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

---

解题过程

相似题目
LeetCode.283.Move Zeroes 将数组中的零移到末尾
LeetCode.027.Remove Element 从数组中移除指定元素
LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项
LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

SolutionV2018

读完题意就想到用交换，类似冒泡排序，把0逐渐都换到后面去，把非0换到前面，写了一版通过了，但非常慢，只打败了1.3%的代码：

class Solution {
    public void moveZeroes(int[] nums) {
        boolean swaped=true;//上次循环是否有过交换
        for(int i=1; i<nums.length && swaped; i++){
            swaped = false;
            for(int j=0; j<nums.length-i; j++){
                if(nums[j]==0 && nums[j+1]!=0){//交换
                    swaped=true;
                    nums[j] = nums[j] ^ nums[j+1];
                    nums[j+1] = nums[j] ^ nums[j+1];
                    nums[j] = nums[j] ^ nums[j+1];
                }
            }
        }
    }
}

基本上就是冒泡排序的套路，O(n^2)复杂度，很慢。

然后看Solution，给出了3个逐渐优化的方法：
第一种方法是不用任何技巧，新申请一个等长数组，先把非零元素逐个放进去，再把后面都补上0，最后赋值给原数组。当然这个方法不符合题中原地操作(in-place)的要求。
第二种方法，双指针，从前往后遍历数组，用慢指针k表示第k+1个非零元素的最终位置，由于所有非零元素肯定最终都排在数组前面，所以只要遍历到一个非零元素就可以放到nums[k]中。最后把剩下的(nums.length-k)个元素赋值为0即可。O(n)复杂度，很不错的方法了。

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length < 2) return;
        int k = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) {
                nums[k++] = nums[i];
            }
        }
        for(;k < nums.length; k++)
            nums[k] = 0;
    }
}

对第二种方法，有一个优化，就是在一趟遍历过程中就将剩下的位置设为0，不需要最后再单独来一遍。里面的思想是，当右指针大于左指针时，说明右指针和左指针之间有0，这时候才需要把非零值换到前面，同时，把右指针位置设为0，省的最后再来一遍：

public void moveZeroes(int[] nums) {
    int leftMostZeroIndex = 0; // The index of the leftmost zero
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            if (i > leftMostZeroIndex) { // There are zero(s) on the left side of the current non-zero number, swap!
                nums[leftMostZeroIndex] = nums[i];
                nums[i] = 0;
            }

            leftMostZeroIndex++;
        }
    }
}

第三种方法，还是第二种方法的优化，但比较难懂，每次遍历到非零值时，左右指针的值交换。想要弄明白为什么交换，得分开分析：
1、left==right时，表明right左边没有0值出现，其实这时没必要交换，当然做一下交换也不会出错。
2、left<right时，说明右指针right左边出现了0值，此时0值肯定在left位置，即nums[left]==0，所以这个left,right交换动作其实相当于nums[left]=nums[right]; nums[right]=0;
所以这个第三种方法和上面的第二种方法的优化是一样的，只是写法不同，写成swap让人比较难懂，而且还少了left==right时不需交换的优化。

class Solution {
    public void moveZeroes2(int[] nums) {
        for(int left = 0,right=0; right < nums.length; right++)
            if (nums[right] != 0){
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
    }
}

SolutionV2020

private static  class SolutionV2020 {
    public void moveZeroes(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        // left左边是要保留的非零元素
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                if (right != left) {
                    nums[left] = nums[right];
                }
                left++;
            }
        }
        // left右边的元素置为0
        while (left < nums.length) {
            nums[left++] = 0;
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_283_MoveZeroes.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_283_MoveZeroes.java

---