# 0026. 刪除排序數組中的重復項 ## 題目地址(26. 刪除排序數組中的重復項) <https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/description/> ## 題目描述 給定一個排序數組，你需要在 原地 刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。 不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。 示例 1: 給定數組 nums = \[1,1,2\], 函數應該返回新的長度 2, 并且原數組 nums 的前兩個元素被修改為 1, 2。 你不需要考慮數組中超出新長度后面的元素。 示例 2: 給定 nums = \[0,0,1,1,1,2,2,3,3,4\], 函數應該返回新的長度 5, 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。 你不需要考慮數組中超出新長度后面的元素。 說明: 為什么返回數值是整數，但輸出的答案是數組呢? 請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對于調用者是可見的。 你可以想象內部操作如下: ``` <pre class="calibre18">``` <span class="hljs-title">// nums 是以“引用”方式傳遞的。也就是說，不對實參做任何拷貝</span> <span class="hljs-keyword">int</span> len = removeDuplicates(nums); <span class="hljs-title">// 在函數里修改輸入數組對于調用者是可見的。</span> <span class="hljs-title">// 根據你的函數返回的長度, 它會打印出數組中該長度范圍內的所有元素。</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < len; i++) { print(nums[i]); } ``` ``` ## 前置知識 - [數組](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - 雙指針 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 - bloomberg - facebook - microsoft ## 思路 使用快慢指針來記錄遍歷的坐標。 - 開始時這兩個指針都指向第一個數字 - 如果兩個指針指的數字相同，則快指針向前走一步 - 如果不同，則兩個指針都向前走一步 - 當快指針走完整個數組后，慢指針當前的坐標加 1 就是數組中不同數字的個數  （圖片來自： <https://github.com/MisterBooo/LeetCodeAnimation>) > 實際上這就是雙指針中的快慢指針。在這里快指針是讀指針， 慢指針是寫指針。 ## 關鍵點解析 - 雙指針 這道題如果不要求，O(n) 的時間復雜度， O(1) 的空間復雜度的話，會很簡單。 但是這道題是要求的，這種題的思路一般都是采用雙指針 - 如果是數據是無序的，就不可以用這種方式了，從這里也可以看出排序在算法中的基礎性和重要性。 - 注意 nums 為空時的邊界條件。 ## 代碼 - 語言支持：JS，Python，C++ Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {number} */</span> <span class="hljs-keyword">var</span> removeDuplicates = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">const</span> size = nums.length; <span class="hljs-keyword">if</span> (size == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> slowP = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> fastP = <span class="hljs-params">0</span>; fastP < size; fastP++) { <span class="hljs-keyword">if</span> (nums[fastP] !== nums[slowP]) { slowP++; nums[slowP] = nums[fastP]; } } <span class="hljs-keyword">return</span> slowP + <span class="hljs-params">1</span>; }; ``` ``` 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-keyword">if</span> nums: slow = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> fast <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, len(nums)): <span class="hljs-keyword">if</span> nums[fast] != nums[slow]: slow += <span class="hljs-params">1</span> nums[slow] = nums[fast] <span class="hljs-keyword">return</span> slow + <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">removeDuplicates</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums)</span> </span>{ <span class="hljs-keyword">if</span>(nums.empty()) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> fast,slow; fast=slow=<span class="hljs-params">0</span>; <span class="hljs-keyword">while</span>(fast!=nums.size()){ <span class="hljs-keyword">if</span>(nums[fast]==nums[slow]) fast++; <span class="hljs-keyword">else</span> { slow++; nums[slow]=nums[fast]; fast++; } } <span class="hljs-keyword">return</span> slow+<span class="hljs-params">1</span>; } }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。