题目来源：https://leetcode.com/problems/move-zeroes/
题目难度：Easy
解答1[Java]：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import java.util.ArrayList;
class Solution {
public void moveZeroes(int[] nums) {
ArrayList<Integer> nonZeroElements = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nonZeroElements.add(Integer.valueOf((nums[i])));
}
}
for (int i = 0; i < nonZeroElements.size(); i++) {
nums[i] = nonZeroElements.get(i).intValue();
}
for (int i = nonZeroElements.size(); i < nums.length; i++) {
nums[i] = 0;
}
}
}
|
复杂度分析
时间复杂度：$O(n)$
空间复杂度：$O(n)$
解答2[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 k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
if (k != i) {
nums[k++] = nums[i];
} else {
k++;
}
}
}
for (int i = k; i < nums.length; i++) {
nums[i] = 0;
}
}
}
|
第 6 到 10 行有一个判断：
1
2
3
4
5
| if (k != i) {
nums[k++] = nums[i];
} else {
k++;
}
|
这个判断其实可以不要，因为只要遇到第一个 0 元素之后，后边的判断就是多余的了。不如改为直接赋值。加上了判断就一定会判断 n 次，但是如果直接赋值，多余的赋值操作的次数是少于 n 次的，所以开销更小。
所以 5-11 行可以直接改为：
1
2
3
4
| if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
|
复杂度分析
时间复杂度：$O(n)$
空间复杂度：$O(1)$
对末尾加零的操作优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public void moveZeroes(int[] nums) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
if (k != i) {
nums[k++] = nums[i];
nums[i] = 0;
} else {
k++;
}
}
}
}
}
|