leetcode刷題記錄--【80 Remove Duplicates from Sorted Ar

haobowd 發布于2019-08-19 11:46 / 2922人閱讀

摘要：給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。正確思路對于每一個元素，都進行移動。或者比較不到最后一個對象。

給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。

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

錯誤思路：
由26題跳過一個的思路，很自然的聯想到跳過2個即可。但是對于{0，0,1,1,1,1,2,3,3}這種情況，最后一個3無法被放到前面去，結果是{0,0,1,1,2,3,2,3,3}，這是因為錯誤代碼將第一個不同的值移動到正確位置以后，下一個和剛被移動的這個值比對如果相同的話，是要等待下一次移動的，而下一次已經到了數組末尾，不再進行移動操作。
所以增加針對最后一個元素的處理（因為我只想到了最后一個元素可能和剛被移動的元素相同的情況），但是又引發了一個bug，即{1,1,1,2,2,3}->{1,1,2,2,3,3},當全部移動完成后，我會多帶帶去比較最后一個元素是否和剛被移動的相同，相同的話，直接放到剛被正確安放的元素后，這樣就導致了重復數據的出現。

public static int removeDuplicates(int[] nums)
{
    int i = 0, j = 0, count=1;
    for(i = 1; i < nums.length; i++)
    {
        if(nums[i] != nums[j])
        {
            if (count >= 2)
            {
                j = j + 2;
                nums[j] = nums[i];
            }
            else
            {
                j = j + 1;
                nums[j] = nums[i];
            }
            count = 1;
        }
        else
        {
            count++;
        }
    }
    if (nums[nums.length - 1] == nums[j])
    {
        j = j + 1;
        nums[j] = nums[nums.length - 1];
    }
    System.out.println(j+1);
    return j+1;
}

正確思路：

public int removeDuplicates(int[] nums)
{
    int i = 0, j = 0, count=1;
    for(i = 1; i < nums.length; i++)
    {
        if(nums[i] == nums[i-1])
        {
            count++;
        }
        else
        {
            count = 1;
        }

        if (count <= 2)
        {
            j = j + 1;
            nums[j] = nums[i];
        }
    }
    System.out.println(j+1);
    return j+1;
}

1.對于每一個元素，都進行移動。
2.計算相同的個數，相同的數量在2個以上時，就不進行移動
3.不是比較nums[i]和nums[i+1]，因為這樣會導致溢出，參見26題的錯誤思路。或者比較不到最后一個對象。

云服務器 GPU云服務器 Duplicates Sorted Leetcod LeetCode

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

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

leetcode刷題記錄-【26 Remove Duplicates from Sorted Ar

摘要：給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用額外空間的條件下完成。聲明兩個指針，為快指針，為慢指針如果遇到相同的數，那么就跳過，。給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組...

heartFollower 2019-08-19 11:46 評論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] Remove Duplicates from Sorted Array 移除有

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

kel 2019-08-14 12:30 評論0 收藏0
[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
leetcode82. Remove Duplicates from Sorted List II

摘要：題目要求翻譯將鏈表中重復的元素全部刪除，返回新的頭結點。相比于，這里將重復的元素全部刪除。除此以外，我們還需要知道重復元素的前一個值和重復元素的最后一個值。如果存在重復值，則跳過重復值后，前節點不變，否則前節點跟隨后節點同時向后移動。題目要求 Given a sorted linked list, delete all nodes that have duplicate number...

崔曉明 2019-08-15 10:36 評論0 收藏0