导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-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.

翻译

给出一个数组nums,编写一个函数,把所有的0都移动到数组的末端,同时保持非零元素的相对顺序。
例如,nums= [0, 1, 0, 3, 12],在调用函数之后,nums应变成 [1, 3, 12, 0, 0]。
注意:
必须原地操作,不能拷贝数组。
最小化总操作次数。

不能新建数组,两种思路:
1、把所有的非0都挪到前面,后面全部赋值0;
2、将排在前面的0和排在后面的非0对调,逐个操作。
因为要最小化操作次数,所以选择第二种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void moveZeroes(int[] nums) {
int zeroIndex = -1, i = 0;
while (i < nums.length) {
if (nums[i] != 0 && zeroIndex < i) {
i++;
continue;
}
zeroIndex = i;
while (true) {
if (++i == nums.length)
return;
if (nums[i] == 0)
continue;
nums[zeroIndex] = nums[i];
nums[i] = 0;
i = zeroIndex + 1;
break;
}
}
}

代码不简洁,而且运行时间为21ms………

参考网上资料,基本两个嵌套循环的算法都可以淘汰掉了……
但思路都是两个指针:
第一种:不断把非0数向前压缩。
一个指针不断向后遍历,另一个指针指向最后一个非零数,一次遍历之后,将最后一个非零数之后的数都置为0。

1
2
3
4
5
6
7
8
9
public void moveZeroes(int[] nums) {
int lastNonZeroIndex = 0;
for (int i = 0; i < nums.length; i++)
if (nums[i] != 0)
nums[lastNonZeroIndex++] = nums[i];

while (lastNonZeroIndex < nums.length)
nums[lastNonZeroIndex++] = 0;
}

第二种:还是两个指针,快指针每次前进,慢指针不为0时前进,遇到0时暂停,当快指针遇到非0数时与慢指针交换,保证快慢指针之间永远只有0,当快指针到尾端时算法停止:

1
2
3
4
5
6
7
8
9
10
11
12
public void moveZeroes(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[slow] == 0 && nums[fast] != 0) {
nums[slow] = nums[fast];
nums[fast] = 0;
}
if (nums[slow] != 0)
slow++;
fast++;
}
}

参考:
http://segmentfault.com/a/1190000003768716
http://www.oschina.net/code/snippet_2377480_51062