3-liner and "few-operations"


  • 4

    Solution 1

    r is the read index, w is the write index (where the next non-zero number shall be written).

    void moveZeroes(vector<int>& nums) {
        for (int r=0, w=0; r<nums.size(); ++r)
            if (nums[r])
                swap(nums[r], nums[w++]);
    }
    

    Solution 2

    This one potentially uses fewer operations. Think of long a vector without zeros or with a long beginning part without zeros - we can skip that whole part (my above solution and every other solution I've seen instead overwrites that whole part with itself).

    r is the read iterator, w is the write iterator (where the next non-zero number shall be written).

    void moveZeroes(vector<int>& nums) {
        auto w = find(nums.begin(), nums.end(), 0), r = w;
        for (; r != nums.end(); ++r)
            if (*r)
                swap(*r, *w++);
    }
    

    Slight variation:

    void moveZeroes(vector<int>& nums) {
        auto w = find(nums.begin(), nums.end(), 0), r = w;
        for (; r != nums.end(); ++r)
            if (*r)
                *w++ = *r;
        fill(w, r, 0);
    }
    

    Got the idea to use r instead of nums.end() in the fill from apolloydy's solution.


    Solution 3

    This one doesn't count (it uses "a temporary buffer" if it can), I just want to mention it anyway.

    void moveZeroes(vector<int>& nums) {
        stable_partition(begin(nums), end(nums), [](int i){return i;});
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.