[Leetcode] Remove Duplicates from Sorted Array 移除有

kel 發布于2019-08-14 12:30 / 459人閱讀

摘要：雙指針法復雜度時間空間思路我們可以將不重復的序列存到數列前面，因為不重復序列的長度一定小于等于總序列，所以不用擔心覆蓋的問題。代碼雙指針法復雜度時間空間思路思路和上題一樣，區別在于記錄前兩個遍歷到的數字來幫助我們判斷是否出現了第三遍。

Remove Duplicates from Sorted Array I

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2], 
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn"t matter what you leave beyond the new length.

雙指針法 復雜度

時間 O(N) 空間 O(1)

思路

我們可以將不重復的序列存到數列前面，因為不重復序列的長度一定小于等于總序列，所以不用擔心覆蓋的問題。具體來說，用兩個指針，快指針指向當前數組遍歷到的位置，慢指針指向不重復序列下一個存放的位置，這樣我們一旦遍歷到一個不重復的元素，就把它復制到不重復序列的末尾。判斷重復的方法是記錄上一個遍歷到的數字，看是否一樣。

代碼

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0) return 0;
        int dup = nums[0];
        int end = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i]!=dup){
                nums[end] = nums[i];
                dup = nums[i];
                end++;
            }
        }
        return end;
    }
}

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn"t matter what you leave beyond the new length.

雙指針法 復雜度

時間 O(N) 空間 O(1)

思路

思路和上題一樣，區別在于記錄前兩個遍歷到的數字來幫助我們判斷是否出現了第三遍。如果當前數字和前一個數字的前一個一樣的話，說明出現了第三次。

代碼

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2) return nums.length;
        int dup1 = nums[0];
        int dup2 = nums[1];
        int end = 2;
        for(int i = 2; i < nums.length; i++){
            if(nums[i]!=dup1){
                nums[end] = nums[i];
                dup1 = dup2;
                dup2 = nums[i];
                end++;
            }
        }
        return end;
    }
}

Follow Up 后續

Q：如果數組沒有排序的話如何解？
A：可以先將其排序再用同樣方法求解，然而時間復雜度將達到O(NlogN)，如果我們改用哈希表或集合來記錄數字出現次數，可以用O(N)空間得到O(N)的時間。

云服務器 GPU云服務器 sorted-array Duplicates Sorted LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64521.html

[LintCode/LeetCode] Remove Duplicates from Sorted

摘要：思路原數組長度為，則返回原數組長度不為，則至少有個元素。將所有不重復的數值賦給，而當和相等時，不做處理。最后返回的就是不同元素的個數，也是新數組的長度。只有在時，才對賦值。注意，每次初始化的時候要分兩種情況，這就意味著從的時候開始遍歷。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

WalkerXu 2019-08-14 15:32 評論0 收藏0
leetcode80. Remove Duplicates from Sorted Array II

摘要：思路與代碼其實在這里我們仍然延續中的思路。在遇到非重復值以及非多余的重復值時，將數值移動到當前記錄的下標上。保證該下標前的值均為滿足題目條件的值。第一次我使用了來記錄某個值出現的次數。題目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...

CoderDock 2019-08-15 10:42 評論0 收藏0
leetcode 26 Remove Duplicates from Sorted Array

摘要：題目比較簡單，就是找出數組不重復的數字，返回不重復的數字個數。無需刪除重復數字，只需要保證數組的前位為不重復的個數字即可代碼如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...

alaege 2019-08-14 18:07 評論0 收藏0
?LeetCode 26：刪除排序數組中的重復項 Remove Duplicates from So

給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...

Alan 2019-08-16 18:35 評論0 收藏0
?LeetCode 26：刪除排序數組中的重復項 Remove Duplicates from So

給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...

cnTomato 2019-07-31 11:28 評論0 收藏0