<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>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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)一共有四道題: ![](https://img.kancloud.cn/49/97/4997522f0fce932eb0f6739061dd0c6a_1194x446.jpg) 這道題是[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 走到頭,說明我們已無數字可寫。 圖解(紅色的兩個數字,表示我們需要比較的兩個數字): ![](https://img.kancloud.cn/05/8f/058f6cc74cd4e0ef16caf04d4178939a_829x637.jpg) ![](https://img.kancloud.cn/0e/a2/0ea2a4c600cb576c5815afbd2b995b46_586x296.jpg) ## 關鍵點分析 - 快慢指針 - 讀寫指針 - 刪除排序問題 ## 代碼 代碼支持: 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 ![](https://img.kancloud.cn/e2/a0/e2a0ab652b0c9af11b1cd3432301b190_1586x809.jpg) - 1. 刪除排序鏈表中的重復元素 ![](https://img.kancloud.cn/54/6d/546dc5dc49d49344a7fe6cf4b3af72eb_1586x1015.jpg) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_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>

                              哎呀哎呀视频在线观看