FXTi's blog
0%

move-zeroes

Posted on Edited on

Move Zeroes – LeetCode 283

Problem

Description

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        unsigned wri = 0;
        for(unsigned pos = 0; pos != nums.size(); ++pos)
            if(nums[pos])
                nums[wri++] = nums[pos];

        for(; wri != nums.size(); ++wri)
            nums[wri] = 0;
    }
};

思路

老样子的快慢双指针法，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$16$ ms，排名$67.15\%$

Better

思路

使用swap而非赋值，避免之后还需要对0进行单独处理。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$16$ ms，排名$67.15\%$

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
            if (nums[cur]) {
                swap(nums[lastNonZeroFoundAt++], nums[cur]);
            }
        }
    }
};