LeetCode 283. Move Zeros [Easy]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：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++;
                }
            }
        }
    }
}