283. 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:

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

大体意思

将数组中 0 元素移动到数组的末尾，不改变其他元素的顺序；不能 copy 数组，最小化的操作

自己的思路

交换冒泡

public static void moveZeroes(int[] nums) {

 boolean hasChange = false;
 do {
  hasChange = false;
  for (int i = 0; i < nums.length - 1; i++) {
   if (nums[i] == 0 && nums[i + 1] != 0) {
    nums[i] = nums[i + 1];
    nums[i + 1] = 0;
    hasChange = true;
   }
  }
 } while (hasChange);
 System.out.println(Arrays.toString(nums));
}

与 0 换位置，参考了别人的想法

public static void moveZeroes2(int[] nums) {
 int firstZoneIndex = -1;
 for (int i = 0; i < nums.length; i++) {
  if (firstZoneIndex != -1) {
   // 发现了过0
   if (nums[i] != 0) {
    nums[firstZoneIndex] = nums[i];
    nums[i] = 0;
    firstZoneIndex++;
   }
  } else {
   // 没有发现过0
   if (nums[i] == 0) {
    firstZoneIndex = i;
   }
  }
 }
 System.out.println(Arrays.toString(nums));
}

别人的算法

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