283. 移动零

Posted on | In
Words count in article: 321 | Reading time ≈ 1

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例1:

1
2
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

示例2：

1
2
输入: nums = [0]
输出: [0]

提示：

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

解法

解法一：

快慢指针

使用快慢指针。i-慢指针指向数组首位，j-快指针遍历数组，遇到不为0的数据，就将该数据移到i处，i自增

最后将i-nums.length区间内的数据全置为0，即可。

JAVA

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

解法二：

快慢指针优化

在上一个解法中，遇到不为0的数据时不仅仅只移动一个位置，而是把两个位置交换，这样就可以略去i-nums.length的再次遍历了。

Java

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