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

heartFollower 發布于2019-08-19 11:46 / 451人閱讀

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

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

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

劃重點：1.排序數組 2.原地刪除

錯誤思路：
1.聲明一個tmp，初始就是nums[0]，用作被比較的對象
2.用tmp去和每一個后面的數去對比，相同的跳過，不同的，先把nums[j]設成tmp,然后j++，tmp變成不同的那個數
錯誤點：
1.使用了新的內存空間，是錯誤的
2.tmp要和后面的數去比，tmp如果走到了最后一個，那么后面必然會產生越界。
3.tmp最后一定是一個和前面不同的數，這個數不參與比較，那么一定不會被覆蓋寫入數組
比如{1,1,2,2,3,3}->{1,2,2,2,3,3}

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

思路：
要求原地刪除，那么一定使用快慢指針進行元素的覆蓋操作。
聲明兩個指針，i為快指針，j為慢指針
如果遇到相同的數，那么就跳過，i++。
如果遇到不同的數，將這個值的下一個數給替換成這個不一樣的值。

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

    }
    System.out.println(j+1);
    return j+1;
}

代碼寫的不夠優雅，因為判斷相等然后continue是沒有必要的，優化一下：

public static int removeDuplicates(int[] nums)
{
    int j = 0;
    for(int i = 1; i < nums.length; i++)
    {
        if(nums[j] != nums[i])
        {
            j++;
            nums[j] = nums[i];
        }

    }
    return j+1;
}

復雜度分析：
遍歷一遍，時間復雜度o(n)
空間復雜度，o(1)

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

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

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

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

摘要：給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。正確思路對于每一個元素，都進行移動。或者比較不到最后一個對象。給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素最多出現兩次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。錯誤思路：由26題跳過一個的思...

haobowd 2019-08-19 11:46 評論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
leetcode83 Remove Duplicates from Sorted List從有序鏈表

摘要：題目要求從有序鏈表中刪除重復的數字，并且返回刪除后的頭結點例如輸入鏈表為返回這題和相似，只是數據結構從數組變成了鏈表若還有更好的思路，請多多指教想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾題目要求：從有序鏈表中刪除重復的數字，并且返回刪除后的頭結點例如輸入鏈表為1->1->2,返回1->2 這題和leetcode26相似，只是數據結構從數組變成了鏈表 /*...

JessYanCoding 2019-08-14 17:52 評論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
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