Move Zeros

题目：
一个数组中将所有的非零元素移动到数组最前面，返回零的个数，
比如[1,0,3,0,4,5,0,1] => [1,3,4,5,1, X,X,X] 顺序不要紧，移动之后数组后面几个元素可以是任意值
要求移动次数最少

解法：
两种情况，

第一种，如果数组中大部分是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;
}

第二种情况，如果数组中大部分是非0的情况，以上方法会让大部分数字重新赋值，所以移动次数多
这时候我们可以采用类似sort colors的做法，使用two pointers使移动次数最少
但是这种方法会打乱原数组的relative order
public class MoveZeroBack {
	public static void moveZeroBack(int[] nums) {
		if (nums == null || nums.length == 0) {
			return;
		}
		int start = 0;
		int end = nums.length - 1;
		while (start <= end) {
			if (nums[end] == 0) {
				end--;
				continue;
			}
			if (nums[start] != 0) {
				start++;
				continue;
			}
			
			//minimize write operations
			nums[start] = nums[end];
			end --;
			//swap(nums, start, end);
		}
	}
	
	private static void swap(int[] nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
	
	private static void printArray(int[] nums) {
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + " ");
		}
		System.out.println();
	}
}