Move Zeroes题目: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:
You must do this in-place without making a copy of the array.
Minimize the total number ofOperations.
一开始的想法是，遍历数组，遇到0就往后移，一直移动最后一步。代码如下
public class Solution {
public static void moveZeroes(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0 && i != (nums.length - 1)) {
for (int j = i; j < nums.length - 1; j++) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
}
但是，发现001这个测试用例不对。
恩，发现问题了，因为第一个数为0，第二个0就没办法移动到最后了。
换一种思路，不遍历找0，而是遍历找非0，遇到非0，且不在第一位，就往前移，直到它前面不是0为止。
public class Solution {
public static void moveZeroes(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0 && i != 0) {
for (int j = i; j > 0 && nums[j - 1] == 0; j--) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
}
}
这样就解决了
其他方法
public static void moveZeroes(int[] nums) {
int i = 0, j = 0;
for (i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
if (j != i) {
nums[j] = nums[i];
nums[j] = 0;
}
j++;
}
}
}
这种方法i遍历数组，只有当i指向为非0时，且ji不同时，j后移，将j处的数改成i处的数，并使i处的数字为0，ij同步后移，而当i指向为0时，只有i后移，j仍然指向0处。
还有一种更简单的方法
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) return;
int insertPos = 0;
for (int num: nums) {
if (num != 0) nums[insertPos++] = num;
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}