# 0080. 刪除排序數組中的重復項 II ## 題目地址（80.刪除排序數組中的重復項 II） <https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。 不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。 示例 1: 給定 nums = [1,1,1,2,2,3], 函數應返回新長度 length = 5, 并且原數組的前五個元素被修改為 1, 1, 2, 2, 3 。 你不需要考慮數組中超出新長度后面的元素。 示例 2: 給定 nums = [0,0,1,1,1,1,2,3,3], 函數應返回新長度 length = 7, 并且原數組的前五個元素被修改為 0, 0, 1, 1, 2, 3, 3 。 你不需要考慮數組中超出新長度后面的元素。 說明: 為什么返回數值是整數，但輸出的答案是數組呢? 請注意，輸入數組是以“引用”方式傳遞的，這意味著在函數里修改輸入數組對于調用者是可見的。 你可以想象內部操作如下: // nums 是以“引用”方式傳遞的。也就是說，不對實參做任何拷貝 int len = removeDuplicates(nums); // 在函數里修改輸入數組對于調用者是可見的。 // 根據你的函數返回的長度, 它會打印出數組中該長度范圍內的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); } ``` ``` ## 前置知識 - 雙指針 ## 公司 - 阿里 - 百度 - 字節 ## 思路 ”刪除排序“類題目截止到現在（2020-1-15）一共有四道題：  這道題是[26.remove-duplicates-from-sorted-array](26.remove-duplicates-from-sorted-array.html) 的進階版本，唯一的不同是不再是全部元素唯一，而是全部元素不超過 2 次。實際上這種問題可以更抽象一步，即“刪除排序數組中的重復項，使得相同數字最多出現 k 次” 。 那么這道題 k 就是 2， 26.remove-duplicates-from-sorted-array 的 k 就是 1。 上一題我們使用了快慢指針來實現，這道題也是一樣，只不過邏輯稍有不同。 其實快慢指針本質是讀寫指針，在這里我們的快指針實際上就是讀指針，而慢指針恰好相當于寫指針。”快慢指針的說法“便于描述和記憶，“讀寫指針”的說法更便于理解本質。本文中，以下內容均描述為快慢指針。 - 初始化快慢指針 slow ， fast ，全部指向索引為 0 的元素。 - fast 每次移動一格 - 慢指針選擇性移動，即只有寫入數據之后才移動。是否寫入數據取決于 slow - 2 對應的數字和 fast 對應的數字是否一致。 - 如果一致，我們不應該寫。 否則我們就得到了三個相同的數字，不符合題意 - 如果不一致，我們需要將 fast 指針的數據寫入到 slow 指針。 - 重復這個過程，直到 fast 走到頭，說明我們已無數字可寫。 圖解（紅色的兩個數字，表示我們需要比較的兩個數字）：   ## 關鍵點分析 - 快慢指針 - 讀寫指針 - 刪除排序問題 ## 代碼 代碼支持： Python Python Code： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicates</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> <span class="hljs-title"># 寫指針</span> i = <span class="hljs-params">0</span> K = <span class="hljs-params">2</span> <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums: <span class="hljs-keyword">if</span> i < K <span class="hljs-keyword">or</span> num != nums[i-K]: nums[i] = num i += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> i ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 基于這套代碼，你可以輕易地實現 k 為任意正整數的算法。 ## 相關題目 正如上面所說，相關題目一共有三道（排除自己）。其中一道我們倉庫已經講到了。剩下兩道原理類似，但是實際代碼和細節有很大不同，原因就在于數組可以隨機訪問，而鏈表不行。 感興趣的可以做一下剩下的兩道鏈表題。 - 1. 刪除排序鏈表中的重復元素 II  - 1. 刪除排序鏈表中的重復元素  大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。