題目

題目鏈接：https://leetcode.cn/problems/remove-element/

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素。元素的順序可能發生改變。然后返回 nums 中與 val 不同的元素的數量。
假設 nums 中不等于 val 的元素數量為 k，要通過此題，您需要執行以下操作：

• 更改 nums 數組，使 nums 的前 k 個元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3,,,_]
解釋：你的函數應該返回 k = 5，并且 nums 中的前五個元素為 0,0,1,3,4。注意這五個元素可以任意順序返回。你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。

class Solution {
public:int removeElement(vector<int>& nums, int val) {}
};

思路 && 代碼

1. 采用暴力移除方法

#include <vector>
#include <iostream>
using namespace std;class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for(int i = 0; i < size; i++) {if(nums[i] == val) {for(int j = i + 1; j < size; j++){ // 此處是 j = i + 1, 且條件是 j < size，nums[j - 1] = nums[j]; // 所以此處必須是 nums[j-1] = nums[j],而不是nums[j] = nums[j+1]}i--;size--;}}return size;}
};
// @lc code=end
int main() {Solution obj;vector<int> vec = {0,1,2,2,3,0,4,2};int val = 2;int res = obj.removeElement(vec, val);cout << res << endl;
}

時間復雜度：O(n^2)
空間復雜度：O(1)

2. 雙指針

第一版代碼：

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();int slowIndex = 0;int fastIndex = 0;while(fastIndex < size){if(nums[fastIndex] == val){fastIndex++;}else{nums[slowIndex] = nums[fastIndex];slowIndex++;}fastIndex++;}return slowIndex;}
};

第二版代碼： 將以上代碼相同類歸化后

class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();int slowIndex = 0;int fastIndex = 0;while(fastIndex < size){if(nums[fastIndex] != val){nums[slowIndex] = nums[fastIndex];slowIndex++;}fastIndex++;}return slowIndex;}
};

時間復雜度：O(n)
空間復雜度：O(1)

總結

簡潔明了的代碼不是一次性就能寫出來的，先把自己想的思路寫出來，調試通后，再看看是否能合并相同的條件和結果，再簡化代碼。