LeetCode 283 - Move Zeroes

Techinpad: [LeetCode] Move Zeroes

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.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should 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.

https://discuss.leetcode.com/topic/29902/1ms-java-solution/6

// Loop through nums, if nums[i] is non-zero, replace the leftmost 
// zero element nums[j] with nums[i] and set nums[i] to zero if i > j. 
// Note that i == j happens when nums has leading non-zero 
// elements, nums = {2, 1, 3, 0, 5, 0, 6}. In this case, we don't perform
// any swap and keep incrementing i and j until i > j.

public void moveZeroes(int[] nums) {
    int j = 0; // The index of the leftmost zero in nums.
    for(int i = 0; i < nums.length; i++){
        if(nums[i] != 0){
            if(i > j){ // i can only be larger than or equal to j.
                nums[j] = nums[i];
                nums[i] = 0;
            }
            j++;
        }
    }
}

Inspired by your code, this is my implementation that doesn't use the temp variable and avoids unnecessary swaps when nums has leading non-zero element.

https://segmentfault.com/a/1190000003768716
http://buttercola.blogspot.com/2015/09/leetcode-move-zeroes.html
https://discuss.leetcode.com/topic/24716/simple-o-n-java-solution-using-insert-index/11

实际上就是将所有的非0数向前尽可能的压缩，最后把没压缩的那部分全置0就行了。比如103040，先压缩成134，剩余的3为全置为0。过程中需要一个指针记录压缩到的位置。

    public void moveZeroes(int[] nums) {
        int cnt = 0, pos = 0;
        // 将非0数字都尽可能向前排
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                nums[pos]= nums[i];
                pos++;
            }
        }
        // 将剩余的都置0
        for(;pos<nums.length; pos++){
            nums[pos] = 0;
        }
    }

https://discuss.leetcode.com/topic/32632/a-95-26-beat-rate-solution

    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int num : nums)
            if (num != 0) nums[j++] = num;
        Arrays.fill(nums, j, nums.length, 0);
    }

https://gist.github.com/gcrfelix/76e265bdc5407fad7d2d

第一种，如果数组中大部分是0的情况，使用remove dups的解法，这样移动次数最少

public int moveZeros(int[] nums) {

  if(nums == null || nums.length == 0) {

    return;

  }

  int index = 0;

  for(int i=0; i<nums.length; i++) {

    if(nums[i] != 0) {

      nums[index++] = nums[i];

    }

  }

  return nums.length - index;

}

public void moveZeroes(int[] nums) { int j = 0; for(int i = 0; i < nums.length; i++) { if(nums[i] != 0) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; j++; } } }
X. http://blog.csdn.net/sbitswc/article/details/48706065

two pointers, one point to first zero element, second point to following first non-zero element.

    public void moveZeroes(int[] nums) {
        if(nums.length<=1) return;
        int first = 0;
        int sec = 0;
        while(sec<nums.length) {
            //find first zero element
            while(first<nums.length && nums[first] !=0) {
                first++;
            }
            if(first == nums.length) return;
            sec = first+1;
            //find following first non-zero element
            while(sec<nums.length && nums[sec] == 0){
                sec++;
            }
            if(sec == nums.length) return;
            swap(nums, first, sec);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

第二种情况，如果数组中大部分是非0的情况，以上方法会让大部分数字重新赋值，所以移动次数多

这时候我们可以采用类似sort colors的做法，使用two pointers使移动次数最少

但是这种方法会打乱原数组的relative order

public int moveZeros(int[] nums) {

  if(nums == null || nums.length == 0) {

    return 0;

  }

  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) {

      int temp = nums[left];

      nums[left] = nums[right];

      nums[right] = temp;

    }

  }

  return nums.length - left;

}

1.     void moveZeroes(vector<int>& nums) {  
2.         int size = nums.size();  
3.         if(size<=1) return;  
4.         int s = 0, e = 0;  
5.           
6.         while(s<size) {  
7.             while( s < size && nums[s] == 0) {  
8.                 s++;  
9.             }  
10.             if(s == size) break;  
11.               
12.             swap(nums[s], nums[e]);  
13.             e++;  
14.             s++;  
15.         }  
16.         return;  
17.     } 

http://blog.welkinlan.com/2015/09/20/move-zeroes-leetcode-java/

    public void moveZeroes(int[] nums) {

        if (nums == null || nums.length == 0) {

            return;

        }

        int numOfNonZero = 0;

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != 0) {

               swap(i, numOfNonZero, nums);

               numOfNonZero++;

            }

        }

    }

    

    private void swap (int i, int j, int[] nums) {

        int t = nums[i];

        nums[i] = nums[j];

        nums[j] = t;

    }

Q：如果要把所有的0放在前面而不是后面呢？
A：同样的解题思路，但是是从后向前遍历，将非0数字压缩到后面。

http://blog.gainlo.co/index.php/2016/11/18/uber-interview-question-move-zeroes/

If you think more about the above solution, there are some redundant operations. When we traverse the array, we don’t really need to finish every single number. When we already reach the last count numbers, there’s no need to check zeroes as all of them should be set to 0.

In other words, the iteration should finish when index i >= count.

First of all, instead of using a counter, we simply use the right pointer that points to the right end of the array, which works exactly the same in essence. Therefore, when left >= right, we can just put everything to 0. This removes redundant operations.

A couple of things you should be careful about the code:

• Validating inputs should always be the first thing in your mind.
• Be cautious about whether it’s left <= right or left < right. (If you use left <= right, you’ll have trouble with input like [1, 2])
• Personally, I’d like to keep code concise. So I won’t add if array[left] == 0 before the swapping.
• In fact, this method modifies the array in-place. Therefore, there’s no need to return the array.

https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/283_Move_Zeros.java

    public void moveZeroes(int[] nums) {
        int now = 0;
        for (int num : nums)
            if (num != 0)
                nums[now ++] = num;
        while (now < nums.length)
            nums[now ++] = 0;
    }

    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i ++)
            if (nums[i] != 0) {
                if (i == j) j ++;
                else {
                    nums[j ++] = nums[i];
                    nums[i] = 0;
                }
            }
    }

1. Follow up 1 - 输出零的数量量

2. 如何保证⾮非零数的顺序

3. with least write