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

給你一個 升序排列 的數(shù)組 nums 璧榄，請你 原地 刪除重復(fù)出現(xiàn)的元素庞溜，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度医增。元素的 相對順序 應(yīng)該保持 一致 蜀漆。

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

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

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

示例1：

輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_]
解釋：函數(shù)應(yīng)該返回新的長度 2 剃毒，并且原數(shù)組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長度后面的元素搂赋。

示例2：

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

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 升序 排列

思路：

本題也是經(jīng)典的雙指針算法題基公，對于一個數(shù)組來說，刪除一個元素是比較復(fù)雜的宋欺，每次刪除元素后轰豆，若要保留原有的順序胰伍，則需要將后面的元素一個個先前“挪”一格位置，這樣操作的話酸休，算法的時間復(fù)雜度是較高的骂租。

所以就有了雙指針法，分為快慢指針法以及左右指針法斑司，能夠?qū)崿F(xiàn)在一個for循環(huán)下完成兩個for循環(huán)的工作渗饮。

而關(guān)于本題，有個很重要的條件就是宿刮，所給定的數(shù)組是有序的互站，是按升序排序的，這就大大簡化了算法的難度僵缺。

而關(guān)于數(shù)組刪除元素相關(guān)的題目胡桃，我們可以避免在中間刪除元素，而是可以想辦法把要刪除的元素換到最后去谤饭，最后一起刪除标捺。

兩遍循環(huán)：

我們可以利用一種最樸素的方法，即暴力地使用兩遍for循環(huán)進行求解揉抵，外層的for循環(huán)用于查找重復(fù)的元素亡容，當尋找到重復(fù)的元素后，利用內(nèi)層的for循環(huán)冤今，將數(shù)組集體向前移動一位闺兢。

 //暴力解法
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        for (int i = 0; i < size-1; i++) {
            if (nums[i] == nums[i+1]) { // 發(fā)現(xiàn)重復(fù)的元素
                for (int j = i + 1; j < size; j++) { //將數(shù)組集體向前移動一位
                    nums[j - 1] = nums[j];
                }
                i--; // 因為下標i以后的數(shù)值都向前移動了一位，所以i也向前移動一位
                size--; // 記錄此時的數(shù)組大小
            }
        }
        return size;
    }

本題使用暴力解法在LeetCode上是會超時的戏罢。

這里面有個細節(jié)問題屋谭，就是外層for循環(huán)的結(jié)束條件是i<size-1而不是size，若是size的話會因為之前數(shù)組元素集體向前移動龟糕，導(dǎo)致最后一次遍歷中桐磁，必定出現(xiàn)ums[i] == nums[i+1]，這樣就會導(dǎo)致多刪除一個元素讲岁。由于最后一個元素在前一輪循環(huán)中我擂，已經(jīng)比較過了，所以循環(huán)到size-1即可缓艳。

快慢雙指針：

設(shè)置快慢雙指針校摩，分別指向數(shù)組，完成各自任務(wù)阶淘。

快指針：不停止衙吩，勇往直前，尋找重復(fù)元素

慢指針：用于記錄更新新數(shù)組的下標位置

  int removeDuplicates2(vector<int>& nums) {
        int slow = 0; //初始化慢指針
        for (int fast = 0; fast < nums.size()-1; fast++) { //快指針對整個數(shù)組進行遍歷溪窒，尋找重復(fù)值
            if (nums[fast]!= nums[fast+1]) { //若不為目標值坤塞，更新慢指針冯勉，并賦值給新數(shù)組
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //最后一位另外作討論
        nums[slow] = nums[nums.size()-1];
        slow++;
        return slow;
    }

這里我用的是將遍歷到的數(shù)組元素與它后面一位的元素作比較，若是兩元素相等尺锚，則不更新slow指針珠闰，若是和后一位不等，說明是不重復(fù)的新元素瘫辩，更新slow指針伏嗜。

這么做有一個弊端：數(shù)組的最后一位沒有后一位元素。所以最后一位要單獨拿出來考慮伐厌，由于沒有后一位元素承绸，數(shù)組的最后一位必定是不重復(fù)的新元素，可以直接加入到slow新數(shù)組中挣轨，這里我是將循環(huán)結(jié)束條件設(shè)為fast < nums.size()-1,然后再循環(huán)結(jié)束后军熏，單獨將最后一位添加至slow對應(yīng)的新數(shù)組中。

當然卷扮，為了很好地規(guī)避這個問題荡澎，我們可以使用后一位與前一位作比較的方法，這個時候晤锹，數(shù)組為空的情況要拿出來單獨討論：

//來自leetcode官方題解 
int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
}

進一步優(yōu)化版：

經(jīng)過進一步思考發(fā)現(xiàn)摩幔，只需將快慢指針所對應(yīng)的值進行比較即可。

  //最終優(yōu)化版
     int removeDuplicates4(vector<int>& nums) {
         int n = nums.size();
         if (n == 0) return 0;
         int slow = 0;
         for (int fast = 0; fast < n; fast++) {
             if (nums[slow] != nums[fast]) {
                 nums[++slow] = nums[fast];
             }
         }
         return slow + 1;
     }

后續(xù)也會堅持更新我的LeetCode刷題筆記鞭铆，歡迎大家關(guān)注我或衡，一起學習。
如果這篇文章對你有幫助车遂，或者你喜歡這篇題解封断，可以給我點個贊哦。
CSDN同步更新舶担，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學習筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主

往期回顧：
LeetCode27.移除元素