【LeetCode】 283. Move Zeroes

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.
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

給一數字陣列nums，請撰寫一個function將所有的0移到非零數的後面。
注意：你應該要更改原陣列而不是複製一份新的。
盡可能最小化你的步驟。

Example:

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Solution

• 先記錄原陣列大小，跑一次將0移除，再將0加回陣列的尾巴直到陣列大小回復。
• 時間複雜度為O(n)。
• 原本以為使用erase會導致速度緩慢，不過實際出來的結果還不錯。

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int s = nums.size();
        int count = 0;
        for(int i = 0;i<s-count;)
        {
            if(nums[i]==0)
            {
                nums.erase(nums.begin()+i);
                count++;
            }
            else
                i++;
        }
        for(int i = 0;i<count;i++)
            nums.push_back(0);
    }
};

tags: LeetCode C++