题目描述
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
1
2
| 输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
|
示例 2:
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
解题思路
两次遍历
我们创建两个指针 i 和 j，第一次遍历的时候指针 j 用来记录当前有多少 非0 元素。即遍历的时候每遇到一个 非0 元素就将其往数组左边挪，第一次遍历完后，j 指针的下标就指向了最后一个 非0 元素下标。
第二次遍历的时候，起始位置就从 j 开始到结束，将剩下的这段区域内的元素全部置为 0。
一次遍历
这里参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点 x，然后把所有小于等于 x 的元素放到 x 的左边，大于 x 的元素放到其右边。
这里我们可以用 0 当做这个中间点，把不等于 0(注意题目没说不能有负数)的放到中间点的左边，等于 0 的放到其右边。
这的中间点就是 0 本身，所以实现起来比快速排序简单很多，我们使用两个指针 i 和 j，只要 nums[i]!=0，我们就交换 nums[i] 和 nums[j]。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Solution283Case1 {
public static void moveZeroes(int[] nums) {
if (null == nums) {
return;
}
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}
for (int i = j; i < nums.length; i++) {
nums[i] = 0;
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
for (int num : nums) {
System.err.println(num);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Solution283Case2 {
public static void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public static void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
for (int num : nums) {
System.err.println(num);
}
}
}
|