LeetCode 27. Remove Element [Easy] [C++] 解題筆記

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

EX:

        Given nums = [0,1,2,2,3,0,4,2], val = 2,

    Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
    Note that the order of those five elements can be arbitrary.
    It doesn't matter what values are set beyond the returned length.

想法:

    這題跟 26. Remove Duplicates from Sorted Array 概念很像，直接遍歷然後把不是 target value 的

值覆蓋到 array 前面即可，另外這題有個可以優話的地方，就是反過來做，遇到等於 target value 的元素時，用 array 的

尾端的元素將它蓋掉(刪除)，然後再從這個元素開始繼續遍歷，這樣在需要刪除的元素較少時可以節省一些 copy 的 overhead。

完整程式碼:

解法一:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int j = 0;
        for (size_t i = 0; i < nums.size(); i++) {
            if (nums.at(i) != val) {
                nums.at(j) = nums.at(i);
                j++;
            }
        }   
        return j;
    }
};

解法二:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int back = nums.size();
        int i = 0;
        while (i < back) {
            if (nums.at(i) == val) {
                nums.at(i) = nums.at(back-1);
                back--;
            }
            else {
                i++;
            }
        }   
        return back;
    }
};