283. Move Zeroes (Easy)

Given an arraynums, write a function to move all0's to the end of it while maintaining the relative order of the non-zero elements.

For example, givennums = [0, 1, 0, 3, 12], after calling your function,numsshould be[1, 3, 12, 0, 0].

Note:

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

Solution 1: 同向Two Pointers O(n); O(1) 从左往右

    /**
     * 同向Two Pointers O(n); O(1) 从左往右
     * Use 2 pointers, left and right, both of which start from the left of the array
     * The right pointer traverses the array, if find a nonzero element, 
     * swap it with the element at the left pointer. Then move the left pointer to right by one.
     * 要注意：左指针指向的元素不一定是0。只有当右指针遇见0时，左指针才会指向0。否则会和右指针一起移动。比如[1,1,0,1,1]
     * When the right pointer finishes the traverse, 
     * the left pointer will point to the start of zero sequence.
     * 下面的注释有问题，不用看
     * Use 2 pointers, left and right, to maintain a window in which all elements are zero.
     * left point to zero's start(遇到0不动，遇到非0先换后动), right points to zero's end(遇到0动，遇到非0先换后动)
     * All elements between the left and right pointer are zeroes.
     */
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) { 
                //要找不是0的元素，来和前面的0交换，但是前面不一定是0，这种情况下left和right指向同一个数
                int temp = nums[left];
                nums[left] = nums[right]; //swap the nonzero number to left
                nums[right] = temp;
//                nums[left] = nums[right]; //这种写法是错误的，因为nums[left]可能不是0
//                nums[right] = 0; //比如这个例子：[1,0]; [1,1,1]
                left++;
            }
        }
    }

Follow Up:

1. move Zero到前面，move One到后面，不改变顺序

       /**
        * 同向Two Pointers O(n); O(1) 从右往左
        */
       public void moveZeroesB(int[] nums) {
           int right = nums.length - 1;
           for (int left = nums.length - 1; left >= 0; left--) {
               if (nums[left] != 0) {
                   int temp = nums[left];
                   nums[left] = nums[right]; 
                   nums[right] = temp; //swap the nonzero number to right
                   right--;
               }
           }
       }
   

2. 将所有的非零元素移动到数组最前面，返回零的个数(有时也会要求返回非0的个数)，比如[1,0,3,0,4,5,0,1] => [1,3,4,5,1, X,X,X] 顺序不要紧，移动之后数组后面几个元素可以是任意值, 要求最小化写入次数。 区别：Move zeros要求把所有的0移动到数组的后面，这题不需要，只需要把非零元素移动到数组前面，而且不要求保持顺序

       /**
       * 相向Two Pointers O(n); O(1)
       */    
       public int moveZeroesC(int[] nums) {
           int left  = 0;
           int right = nums.length - 1;
           while (left < right) {
               while (left < right && nums[left] != 0) {
                   left++;
               }
               while (left < right && nums[right] == 0) {
                   right--;
               }
               if (left < right) {
                   nums[left++] = nums[right--]; //将非0数移到前面，right位置上非0数不用管
               }
           }
           return left; //非0的个数
   //        return nums.length - left; //0的个数
       }
   

3. after moves, return the number of 0 in the array.