警告
本文最后更新于 2020-04-12，文中内容可能已过时。
给定一个数组 nums，编写一个函数将所有的 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例 1：
1
2
| 输入：[0, 1, 0, 3, 12]
输出：[1, 3, 12, 0, 0]
|
说明：
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
思路及解法
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针只想待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
注意到以下性质：
- 左指针左边均为非零数；
- 右指针左边到左指针处均为零。
代码
Java：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public 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 void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
|
Python：
1
2
3
4
5
6
7
8
9
| class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
|
C：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void swap(int *a, int *b) {
int t = *a;
*a = *b, *b = t;
}
void moveZeroes(int *nums, int numsSize) {
int left = 0, right = 0;
while (right < numsSize) {
if (nums[right]) {
swap(nums + left, nums + right);
left++;
}
right++;
}
}
|
复杂度分析：
- 时间复杂度：$ \rm{O(n)} $，其中$ \tt{n} $是序列长度。每个位置至多被遍历两次。
- 空间复杂度：$ \rm{O(1)} $。只需要常数的空间存放若干变量。