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,移到数组的最后面,其他元素按照数组的前后顺序排列。
要求:不能新建数组,而且最小化操作的次数。
我自己的错误解法
解法是遇到0的时候把这个元素移到最后面,然后其他元素往前移动1位,但是有个问题是,遇到[0,0,1]这种连续几个0的数组时会报错,因为移动之后,0往前移动,但是因为数组+1,所以并没有判断移到0位的数字。
public void moveZeroes (int nums []){
int length = nums.length;
int count = 0;
for (int i = 0; i <= length - 1; i++) {
if (nums[i] == 0 && (i + count < length)) {
count++;
for (int j = i; j <= length - 2 - i; j++) {
nums[j] = nums[j + 1];
}
nums[length - 1 - i] = 0;
}
}
正确解法
讨论区的解法,是遍历数组,然后初始化一个标记值为0,判断数组中不为0元素的索引值,当数组不为0的时候,标记值自增,自增的次数代表 数组不包含为0的元素的索引值,其他不为0的元素只需赋值在这个索引值之后即可。
而在交换数组值的时候,只需要将为0数组的值赋给临时变量,当前不为0的数组值赋给索引值为标记值的数组元素,然后将临时变量赋给之前判断的不为0的数组值。
例如: int [ ] nums = [ 1, 1, 0, 0, 0, 1 ] 判断,cur++ 之后等于2,也即此时数组 nums[0]、nums[1]不为0,其他不为0的元素,只需赋给num[2]即可。而判断语句就是实现这样的功能:
temp = nums [2] , nums[2]=nums[5], nums[5]=temp
public void moveZeroes (int nums []) {
if (nums == null || nums.length == 0) {
return;
}
int cur = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
int temp = nums[cur];
nums[cur++] = nums[i];
nums[i] = temp;
}
}
}
网友评论