027 Remove Element[E]

02-25

1 題目描述

Given an array and a value, 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.
The order of elements can be changed. It doesnt matter what you leave beyond the new length.

題目難度：Easy

2 題目樣例

Given nums = [3,2,2,3], val = 3,Your function should return length = 2, with the first two elements of nums being 2.

3 題意分析

去掉所有重複元素，返回處理完後數組的長度。

類似上次的題，要求原地演算法並且空間複雜度 $O(1)$

4 思路分析

1 STL

不好意思，我覺得這種情況下STL就是最優解（震聲），兩行搞定。

class Solution {public: int removeElement(vector<int>& nums, int val) { auto end = remove(nums.begin(),nums.end(),val); return end - nums.begin(); }};

整體時間複雜度 $O(n)$ ，空間複雜度 $O(1)$

2 手工實現

兩個指針從頭開始，已經遍歷過的數據就沒用了可以直接覆蓋，所以一個指針指向新的數組結尾，一個指針遍歷。

代碼如下

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

整體時間複雜度 $O(n)$ ，空間複雜度 $O(1)$

3 略加優化

從頭開始遍歷，每次遇到和val相等的值的時候直接用數組最後一個元素覆蓋。

代碼如下

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

整體時間複雜度 $O(n)$ ，空間複雜度 $O(1)$

5 後記

三種演算法都只打敗了8%的代碼sad。