<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 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://img.kancloud.cn/9a/2a/9a2a254606bebf736748acb8212755e5_952x532.gif) (圖片來自: <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 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看