「Leetcode簡潔筆記」第26題:刪除排序數組中的重複項

2020-10-10 可愛小男孩76

簡單的喲 (^U^)ノ~YO

本文答案參考自leetcode官方題解。(雖然開了原創[閉嘴][尬笑])


題目有一個特殊要求:必須在 原地 修改輸入數組[震驚]

原地 指的是:不創建新的數組,直接在原來的數組上修改(說的專業點就是 在原來的內存地址上修改)

【方法1】快慢指針

兩個指針,一快一慢。

快是因為每次都 無條件 地向前遍歷

慢是因為每次都要先 判斷是否符合條件 才向前走

在這道題中,(兩個指針當然是從下標0處開始遍歷的啦~)

  1. 快指針每次都向前走
  2. 慢指針進行判斷:
    1. 如果快指針指向的元素慢指針指向的元素 相等,則什麼也不做(慢指針不動),直接進入下一輪循環
    2. 如果快指針指向的元素慢指針指向的元素 相等,則慢指針向前走一格,然後將慢指針指向的元素 改為 快指針指向的元素

移除後重複元素後數組的長度 就是 慢指針指向的元素下標加1 啦[耶]

相關焦點

  • leetcode-第26題-刪除排序數組中的重複項
    //給定一個排序數組,你需要在 原地 刪除重複出現的元素,使得每個元素只出現一次,返回移除後數組的新長度。 // 不要使用額外的數組空間,你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。
  • leetcode C++11題解系列-079 刪除排序數組中的重複項 II
    ,你需要在原地刪除重複出現的元素,使得每個元素最多出現兩次,返回移除後數組的新長度。你不需要考慮數組中超出新長度後面的元素。示例 2:給定 nums = [0,0,1,1,1,1,2,3,3],函數應返回新長度 length = 7, 並且原數組的前五個元素被修改為 0, 0, 1, 1, 2, 3, 3 。你不需要考慮數組中超出新長度後面的元素。
  • LeetCodeK 個一組翻轉鍊表&刪除排序數組中的重複項
    } //連接 pretail.next=node; pretailNext.next=tail; pretail=pretailNext; pretailNext=tail; index=0; } return value.next; }刪除排序數組中的重複項
  • 「Leetcode簡潔筆記」第27題:移除元素
    這也是簡單呢,[翻白眼](感覺出題官有點水,怎麼跟上一題那麼像)本文答案參考自leetcode官方題解。又是原地修改。如果快指針指向的元素與慢指針指向的元素 不相等,則將慢指針指向的元素改為快指針指向的元素,然後慢指針向前走一格(特別注意這裡跟上一題的執行順序是相反的!!!)
  • LeetCode|算法|筆記:第33題:搜索旋轉排序數組
    本文答案參考自leetcode官方題解題目描述假設按照升序排序的數組在預先未知的某個點上進行了旋轉。( 例如,數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。搜索一個給定的目標值,如果數組中存在這個目標值,則返回它的索引,否則返回 -1 。你可以假設數組中不存在重複的元素。你的算法時間複雜度必須是 O(log n) 級別。
  • 「Leetcode簡潔筆記」第14題:最長公共前綴
    本文答案參考自leetcode官方多解 警告!這題的難度是 簡單,但是解法有很多(看這篇幅還以為是難題[捂臉])【方法1】依次比較【時間複雜度:O(m*n) 空間複雜度 O(1)】比較字符串1和字符串2,獲取它們的最長公共前綴,記為 prefix
  • 「Leetcode簡潔筆記」第16題:最接近的三數之和
    題目描述:給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數,使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。本文答案參考自leetcode官方題解這個可以參考上一題【方法1】還是比雙重for循環更暴力的三重for循環【時間複雜度 O(n^3) 空間複雜度 O(1)】啊這個,不用介紹了,數字一多就會超過時間限制了~
  • 面試題-算法:刪除排序數組中的重複項
    算法,有多重要大家都應該知道,如果你有過大廠面試經歷,那就更懂了,今天我們來一道簡單的題,通過這道題學習一個技巧。題目:過濾一個數組中的重複元素,時間複雜度和空間複雜度最優的方式。時間複雜度:只遍歷了一次,O(1);空間複雜度:只多引入一個int變量;思路:我的思路是後一個元素如果不等於前一個元素,則把後一個元素放入當前數組的最新不重複位置
  • 「LeetCode筆記」第35題:搜索插入位置
    簡單的哦[憨笑]8說了,本文答案參考自leetcode官方題解題目描述給定一個排序數組和一個目標值,在數組中找到目標值,並返回其索引。如果目標值不存在於數組中,返回它將會被按順序插入的位置。你可以假設數組中無重複元素。
  • 算法圖解,面試不用怕:刪除排序數組中的重複項(使用雙指針)
    ,你需要在 原地 刪除重複出現的元素,使得每個元素只出現一次,返回移除後數組的新長度。你不需要考慮數組中超出新長度後面的元素。給定 nums = [0,0,1,1,1,2,2,3,3,4],函數應該返回新的長度 5, 並且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。你不需要考慮數組中超出新長度後面的元素。
  • 「Leetcode簡潔筆記」第18題:四數之和
    本文答案參考自leetcode官方題解【方法1】不會吧,不會吧,不會還有人用四重for循環吧?[看]【方法2】排序 + 雙指針【時間複雜度 O(n^3) 空間複雜度 O(log n)】還是跟三數之和的解法相似,不過這次是在兩重循環中使用雙指針(當然得先排序)上圖:
  • leetcode鍊表之刪除排序鍊表中的重複元素
    序本文主要記錄一下leetcode鍊表之刪除排序鍊表中的重複元素題目 給定一個排序鍊表,刪除所有重複的元素,使得每個元素只出現一次。> 示例 1: 輸入: 1->1->2 輸出: 1->2 示例 2: 輸入: 1->1->2->3->3 輸出: 1->2->3 來源:力扣(LeetCode) 連結:https://leetcode-cn.com
  • 「Leetcode簡潔筆記」第23題:合併K個排序鍊表
    本文答案參考自leetcode官方題解。前面是合併兩個,根據leetcode的尿性,肯定有合併多個的,然後它來了。【方法1】挨個挨個地合併你可以把鍊表看成一堆撲克牌,現在有K堆牌,你要想全部排序抓在手裡,你肯定想到的是:先拿一堆,然後再拿一堆將這兩堆牌合併然後再拿下一堆,再合併,再拿下一堆再合併……這樣合併
  • leetcode442_go_數組中重複的數據
    題目給定一個整數數組 a,其中1 ≤ a[i] ≤ n (n為數組長度), 其中有些元素出現兩次而其他元素出現一次。找到所有出現兩次的元素。你可以不用到任何額外空間並在O(n)時間複雜度內解決這個問題嗎?
  • 「Leetcode簡潔筆記」第24題:兩兩交換鍊表中的節點
    本文答案參考自leetcode官方題解。這道題跟前面的【第21題:合併兩個有序鍊表】一樣,也是分遞歸和迭代解法。
  • 網際網路面試題目「貪心算法」K次取反後最大化的數組和
    maximize-sum-of-array-after-k-negations/給定一個整數數組 A,我們只能用以下方法修改該數組:我們選擇某個索引 i 並將 A[i] 替換為 -A[i],然後總共重複這個過程 K 次。
  • leetcode C++11題解系列-081 刪除排序鍊表中的重複元素 II
    題目給定一個排序鍊表,刪除所有含有重複數字的節點,只保留原始鍊表中 沒有重複出現 的數字。->3->4->4->5輸出: 1->2->5示例 2:輸入: 1->1->1->2->3輸出: 2->3解題代碼與測試//// Created by tannzh on 2020/8/19.///* * 刪除排序鍊表中的重複元素
  • 網際網路公司高頻面試題目「回溯算法」求子集問題(二)
    第90題.子集II題目連結:https://leetcode-cn.com/problems/subsets-ii/給定一個可能包含重複元素的整數數組那麼關於回溯算法中的去重問題,「在中已經詳細講解過了,和本題是一個套路」
  • 字節大佬Leetcode刷題筆記,看完吊打問你算法的面試官
    介紹leetcode 題解,記錄自己的 leetcode 解題之路。目前分為五個部分:第一個部分是 leetcode 經典題目的解析,包括思路,關鍵點和具體的代碼實現。第二部分是對於數據結構與算法的總結第三部分是 anki 卡片, 將 leetcode 題目按照一定的方式記錄在 anki 中,方便大家記憶。
  • 網際網路公司高頻面試題目「回溯算法」遞增子序列
    而且本題也要求不能有相同的遞增子序列。這又是子集,又是去重,是不是不由自主的想起了剛剛講過的。就是因為太像了,更要注意差別所在,要不就掉坑裡了!在中我們是通過排序,再加一個標記數組來達到去重的目的。而本題求自增子序列,是不能對原數組進行排序的,排完序的數組都是自增子序列了。