題目：

26. 刪除有序數(shù)組中的重復(fù)項(xiàng)

難度簡(jiǎn)單3054收藏分享切換為英文接收動(dòng)態(tài)反饋

給你一個(gè)?升序排列?的數(shù)組?nums?，請(qǐng)你?原地?刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素?只出現(xiàn)一次?，返回刪除后數(shù)組的新長(zhǎng)度。元素的?相對(duì)順序?應(yīng)該保持?一致?。

由于在某些語(yǔ)言中不能改變數(shù)組的長(zhǎng)度，所以必須將結(jié)果放在數(shù)組nums的第一部分。更規(guī)范地說(shuō)，如果在刪除重復(fù)項(xiàng)之后有?k?個(gè)元素，那么?nums?的前?k?個(gè)元素應(yīng)該保存最終結(jié)果。

將最終結(jié)果插入?nums?的前?k?個(gè)位置后返回?k?。

不要使用額外的空間，你必須在?原地?修改輸入數(shù)組?并在使用 O(1) 額外空間的條件下完成。

判題標(biāo)準(zhǔn):

系統(tǒng)會(huì)用下面的代碼來(lái)測(cè)試你的題解:

int[] nums = [...]; // 輸入數(shù)組 int[] expectedNums = [...]; // 長(zhǎng)度正確的期望答案 int k = removeDuplicates(nums); // 調(diào)用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { ? ?assert nums[i] == expectedNums[i]; }

如果所有斷言都通過(guò)，那么您的題解將被?通過(guò)。

?

示例 1：

輸入：nums = [1,1,2]輸出：2, nums = [1,2]

解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 2 ，并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

示例 2：

輸入：nums = [0,0,1,1,1,2,2,3,3,4]輸出：5, nums = [0,1,2,3,4]

解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 5 ， 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4 。不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

?

提示：

• 1 <= nums.length <= 3 * 104

• -104?<= nums[i] <= 104

• nums?已按?升序?排列

第一種對(duì)法：

class?Solution?{

private:

????map<int,int>?sz;

public:

????int?removeDuplicates(vector<int>&?nums)?{

????????int?fast=0,slow=0;

????????while(fast<nums.size()){

????????????if(sz[nums[fast]]==0){

????????????????sz[nums[fast]]=1;

????????????????nums[slow]=nums[fast];

????????????????slow++;

????????????}

????????????fast++;

????????}

????????return?slow;

????}

};

使用了輔助數(shù)組來(lái)標(biāo)記已經(jīng)遇到過(guò)的數(shù)組，以達(dá)到去重目的，時(shí)間復(fù)雜度O（n）