国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Leecode - 從數(shù)組中刪除重復項

kamushin233 / 671人閱讀

摘要:原文地址題目給定一個排序數(shù)組,你需要在原地刪除重復出現(xiàn)的元素,使得每個元素只出現(xiàn)一次,返回移除后數(shù)組的新長度。示例給定函數(shù)應該返回新的長度并且原數(shù)組的前五個元素被修改為。

原文地址: https://www.luoyangfu.com/art...
題目

給定一個排序數(shù)組,你需要在原地刪除重復出現(xiàn)的元素,使得每個元素只出現(xiàn)一次,返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間,你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

示例 1:

給定數(shù)組 nums = [1,1,2], 

函數(shù)應該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。 

你不需要考慮數(shù)組中超出新長度后面的元素。

示例 2:

給定 nums = [0,0,1,1,1,2,2,3,3,4],

函數(shù)應該返回新的長度 5, 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。

你不需要考慮數(shù)組中超出新長度后面的元素。
說明:

為什么返回數(shù)值是整數(shù),但輸出的答案是數(shù)組呢?

請注意,輸入數(shù)組是以“引用”方式傳遞的,這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。

你可以想象內(nèi)部操作如下:

// nums 是以“引用”方式傳遞的。也就是說,不對實參做任何拷貝
int len = removeDuplicates(nums);

// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中該長度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
思路

根據(jù)題目說明:

排序的數(shù)組 -> 數(shù)組是有序的

原地刪除重復數(shù)組 -> 不能移除

每個元素只出現(xiàn)一次 -> 時間復雜度O(n)

不能使用額外的數(shù)組空間 -> 不能復制元素

不用考慮數(shù)組中超出長度的數(shù)據(jù) -> 和第2條對應,把要移除的元素放到后面

我們需要在 時間復雜度為O(n) 情況下為一個有序的數(shù)組做一個刪除, 我們使用一個計數(shù)變量 i = 0 來標記當前數(shù)組不重復的數(shù)據(jù)的,但是這個時候我們需要 原地刪除 數(shù)組,這個時候就需要重復的數(shù)據(jù)放到后面,這樣返回的數(shù)據(jù)就可以保持在前面 i 個數(shù)據(jù)是不重復的。既然需要和后面元素交換,數(shù)組交換需要兩個下表,我們這里再采用另外一個 計數(shù)變量j 來表示作為當前數(shù)組遍歷計數(shù)變量. 根據(jù)上述描述,我們使用的方法也稱之為雙指針法. 這里i 稱之為慢指針, j 稱之為快指針

雙指針,顧名思義,就是利用兩個指針去遍歷數(shù)組,一般來說,遍歷數(shù)組采用的是單指針(index)去遍歷,兩個指針一般是在有序數(shù)組中使用,一個放首,一個放尾,同時向中間遍歷,直到兩個指針相交,完成遍歷,時間復雜度也是O(n)。
解決方法

根據(jù)解決思路我們這里使用 javascript 語法來開發(fā):

function removeDuplicates(arr) {
    
    if(!Array.isArray(nums) || !nums.length) return 0;
  
    if(nums.length < 2) return 1;
    
    var i = 0;

    for(var j = 1; j < nums.length; j ++) {
    
        if(nums[i] !== nums[j]) {
            i ++; 
            nums[i] = nums[j]
        }
    }
    
    return ++i;
}

上面代碼有兩點要解釋的,判斷 nums[i] !== nums[j] 這里,當他們不相等的時候進行 ij 的位置交換, 當相同的時候j 就跳過相同的元素的, i++ 就在不同的下一個元素進行交換。 在最后返回 ++i 這里,以為 i 是從0開始,因此長度需要+1.

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/104625.html

相關(guān)文章

  • Leecode-3 Longest Substring Without Repeating Char

    摘要:題目解析題目含義很簡單,即求出沒有字符重復的子字符串的長度。例如很明顯就是個由完全重復字符組成的字符串,所以它的答案長度為。所以綜合來看該算法的效率為。 題目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...

    luzhuqun 評論0 收藏0
  • leecode 39 Combination Sum

    摘要:我們需要找出中的數(shù)字的不同組合,使得每一種組合的元素加和為。輸入的候選集和目標數(shù)字結(jié)果集是想法這道題采取了遞歸的思路。每次將一個元素加入的時候,判斷是否滿足中的元素加和等于,如果等于,直接將加入最終返回的結(jié)果集。 題目詳情 Given a set of candidate numbers (C) (without duplicates) and a target number (T),...

    yhaolpz 評論0 收藏0
  • [Leecode] Linked List Cycle 鏈表環(huán)

    摘要:快慢指針法復雜度時間空間思路這是一道非常經(jīng)典的雙指針題。如果快指針和慢指針相遇,則說明鏈表有環(huán)。代碼快慢指針法復雜度時間空間思路這題是基于上一題,上一題我們發(fā)現(xiàn)相遇后就返回了,而這里我們還要繼續(xù)找到環(huán)的起始點。 Linked List Cycle I Given a linked list, determine if it has a cycle in it.Follow up: Ca...

    includecmath 評論0 收藏0
  • LeetCode-Remove Element-排序數(shù)組刪除重復

    摘要:描述給定一個有序數(shù)組,你需要原地刪除其中的重復內(nèi)容,使每個元素只出現(xiàn)一次并返回新的長度。最后慢指針指向的元素及前面所有元素都是不重復的。 描述: 給定一個有序數(shù)組,你需要原地刪除其中的重復內(nèi)容,使每個元素只出現(xiàn)一次,并返回新的長度。不要另外定義一個數(shù)組,您必須通過用 O(1) 額外內(nèi)存原地修改輸入的數(shù)組來做到這一點。示例: 給定數(shù)組: nums = [1,1,2], 你的函數(shù)應該返回新...

    dayday_up 評論0 收藏0
  • 【刷算法】LeetCode.26-排序數(shù)組刪除重復

    摘要:題目描述給定一個排序數(shù)組,你需要在原地刪除重復出現(xiàn)的元素,使得每個元素只出現(xiàn)一次,返回移除后數(shù)組的新長度。示例給定函數(shù)應該返回新的長度并且原數(shù)組的前五個元素被修改為。也就是說,不對實參做任何拷貝在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。 題目描述 給定一個排序數(shù)組,你需要在原地刪除重復出現(xiàn)的元素,使得每個元素只出現(xiàn)一次,返回移除后數(shù)組的新長度。 不要使用額外的數(shù)組空間,你必須在原地修改輸...

    wua_wua2012 評論0 收藏0

發(fā)表評論

0條評論

kamushin233

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<