283. Move Zeroes

1.問題

• 給予一個array nums, 寫一個function可以將所有的0到array的後面

2.想法

• 第一種想法是掃描整個array, 一碰到0就swap到最後面, 但這種作法的複雜度很高

• 第二種做法是只要一碰到不為0的元素, 就直接assign到陣列前方, 並記錄index

3.程式碼

• 第一種做法

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int index = 0, cnt = 0;
        while (cnt < (nums.size())) {
            if (nums[index] == 0){
                for (int i = index; i < nums.size(); i++) {
                    if (nums[i] == 0) {
                        for (int j = i; j < nums.size() - 1; j++) { 
                            swap(nums, j, j + 1);
                        }   
                    }
                }
            } else {
                index++;
            }
            cnt ++;
        }
    }
private:
    void swap(vector<int>& nums, int num1, int num2) {
        int tmp = nums[num1];
        nums[num1] = nums[num2];
        nums[num2] = tmp;
    }
};

• 第二種做法

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

4.Performance

• 第一種做法

• 第二種做法