026 Remove Duplicates from Sorted Array[M]

1 題目描述

Given a sorted array, remove the duplicates in-place such that each element appear only once 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.

難度：Medium

2 題目樣例

Given nums = [1,1,2],Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.It doesnt matter what you leave beyond the new length.

3 題意分析

要求去掉一個數組中所有重複的元素（只留一個），並且返回處理完的數組的長度，要求是原地演算法（定義見超鏈接的wiki）並且空間複雜度 。

這裡有一個很關鍵的條件是輸入數組是有序的。

4 思路分析

從頭遍歷整個數組，只要遇到一種新的數字就在原數組上記錄即可，代碼如下

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

整體時間複雜度 ，空間複雜度 。

等等！還記得STL有個std::unique嗎！（經評論提醒）於是代碼縮減為三行

class Solution {public: int removeDuplicates(vector<int>& nums) { auto it = unique(nums.begin(),nums.end()); nums.resize(it - nums.begin()); return nums.size(); }};

複雜度是一致的，然而加上輸入掛之後打敗了99.58%的代碼！還是STL比較強啊。

5 後記

我怎麼覺得這是個Easy題呢（逃

STL太強了（再逃