The description of the problem

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to cyouhange the length of the array in some languages, you must instead have the result be placed in the first part
of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with constant extra memory.
Custom Judge:
The judge will test your solution with the following code:
Example:
Input: nums = [3, 2, 2, 3], val = 3
Output 2, nums = [2, 2, _, _]
Explanation: Your function should return $k=2$, with the first two elements of nums being 2. It does not matter what you leave beyound the returned k (hence they are underscores).

solution 1 (Brute Force Algorithms)

#include 
#include 
using namespace std;
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // bruce force solution
        // time complexity: O(n)
        // space complexity: O(1)
        int n = nums.size();
        int i = 0;
        for (int i = 0; i < n;) {
            if (nums[i] == val) {
                for (int j = i; j < n - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                n--;
            } else {
                i++;
            }
        }
        return n;
    }
};
int main ()
{
    Solution s;
    vector<int> nums = {3,2,2,3};
    int val = 3;
    int n = s.removeElement(nums, val);
    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

The corresponding results

(base) sunny@sunnydeMacBook-Air testForCpp % ./test
2 2 
1
2

在这里插入图片描述

The solution 2 (two pointers)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        int j = nums.size() - 1;
        while (i <= j) {
            if (nums[i] == val) {
                nums[i] ^= nums[j];
                nums[j] ^= nums[i];
                nums[i] ^= nums[j];
                j--;
            } else {
                i++;
            }
        }
        return j+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

The solution 3 (a pointer points old array, the other pointer points new array)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int slow = 0;
        for (int fast = 0; fast < n; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

The corresponding results