移动零

题意

将数组中的 0 全部移到末尾，同时保持非零元素的相对顺序。要求原地修改。

思路

维护一个 write 指针，指向下一个非零元素应该放置的位置。遍历数组，遇到非零元素就写入 write 位置并递增。遍历结束后，write 之后的位置全部置零。

也可以交换而非覆盖，写法更简洁但多一次赋值。

代码

cpp

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
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 */
// main.cpp：双指针，write 指针收集非零元素，剩余补零。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int> &nums) {
        int w = 0;
        for (int i = 0; i < (int)nums.size(); i++)
            if (nums[i])
                nums[w++] = nums[i];
        while (w < (int)nums.size())
            nums[w++] = 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    Solution().moveZeroes(a);
    for (int x : a)
        cout << x << ' ';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        w = 0
        for i in range(len(nums)):
            if nums[i]:
                nums[w] = nums[i]
                w += 1
        for i in range(w, len(nums)):
            nums[i] = 0


def main() -> None:
    n = int(input())
    nums = list(map(int, input().split()))
    Solution().moveZeroes(nums)
    print(*nums)


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n)，每个元素至多处理一次。
空间复杂度：O(1)，只使用几个指针。

总结

"收集"型双指针适用于把满足某一条件的元素集中到数组前部，剩余位置用默认值填充。

目录

题意

思路

代码

复杂度

总结