LEETCODE刷題記錄【27 Remove Element】

馬龍駒發布于2019-08-19 11:45 / 3165人閱讀

摘要：復雜度分析時間復雜度遍歷次空間復雜度還有沒有優化空間方法在某些特定場景下會進行不必要的復制操作，影響性能。注意尾部的元素有可能是需要剔除的，所以，下一輪循環要從當前索引重新開始。

給定一個數組 nums?和一個值 val，你需要原地移除所有數值等于?val?的元素，返回移除后數組的新長度。

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

元素的順序可以改變。你不需要考慮數組中超出新長度后面的元素。

1.先來寫一個最簡單的版本，即使用額外空間作為輔助，把符合條件的元素寫到一個新的數組里。

public static ArrayList removeElement(int[] nums, int val)
{

    ArrayList newNums = new ArrayList();
    for (int item:nums)
    {
        if(item != val)
        {
            newNums.add(item);
        }
    }
    System.out.print(newNums.size());
    return newNums;
}

基礎知識查漏補缺：
1.Java數組的聲明、初始化和使用
遇到了一個問題，新的數組需要聲明和初始化，但是新數組的長度還不知道，怎么初始化。
考慮使用ArrayList
2.ArrayList的聲明和使用
3.靜態方法中調用非靜態方法的限制

上述方法：
1.需要遍歷數組一次，所以時間復雜度是o(n)
2.需要使用一個數組作為額外空間，所以空間復雜度是o(n)

2.還有沒有優化空間？
進階版本--降低空間復雜度
思路：
方法1需要開辟一個新的數組空間，然而題目中給定的說明，不需要考慮數組中超出長度后面的元素，可以考慮把舊數組的空間再利用。
由于必須要根據索引替換數組的值，所以不能用For-Each循環方法。

public static int removeElement(int[] nums, int val)
{
    int j = 0;
    for (int i = 0;i < nums.length;i++)
    {
        if(nums[i] != val)
        {
            nums[j] = nums[i];
            j++;
        }
    }
    System.out.print(j);
    return j;
}

復雜度分析：
時間復雜度：o(n) 遍歷2n次
空間復雜度:o(1)

3.還有沒有優化空間？
方法2在某些特定場景下會進行不必要的復制操作，影響性能。比如{1,2,3,5,4} val=4，或者{4,1,2,3,5},似乎沒有必要把前4個元素復制一遍，在這一點上可以進行優化，優化思路為如果匹配到需要剔除的元素，就把數組末尾的元素替換到這個位置來。注意：尾部的元素有可能是需要剔除的，所以，下一輪循環要從當前索引重新開始。

public static int removeElement(int[] nums, int val)
{
    int n = nums.length;
    System.out.print(n);
    for (int i = 0;i < n;i++)
    {
        if(nums[i] == val)
        {
            nums[i] = nums[n-1];
            i--;
            n--;
            System.out.println("1:n--:"+n);
        }
    }
    System.out.print(n);
    return n;
}

遇到的問題：
1.在循環里，把nums.length作為了固定長度，會導致所有元素都被遍歷，實際上被替換到前面的元素不需要被遍歷，導致了bug
2.在使用i--時，考慮如果數組前幾個元素都是需要被剔除的元素，會不會導致index為負，導致溢出。經過分析和實驗不會，因為每次循環結束i都要++

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

總結：
1.學會的新方法，雙指針法
2.如果沒有普遍的優化方法，那么就考慮業務場景的特點，比如方法三，針對某些特殊場景提出優化空間。

云服務器 GPU云服務器 Element LeetCode remove LeetCode_String

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

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

leetcode-27. Remove Element

摘要：題目闡釋根據告知的元素，從列表中刪除，并計算剩余元素的個數重點通過移動一個列表的元素，記錄位置，將一個列表內的所有元素分類。題目闡釋：根據告知的元素，從列表中刪除，并計算剩余元素的個數重點：通過移動一個列表的元素，記錄index位置，將一個列表內的所有元素分類。計算剩余元素的個數，也可以看成先分類，再統計。 Given an array nums and a value va...

cgspine 2019-07-30 17:19 評論0 收藏0
leetcode刷題記錄--【80 Remove Duplicates from Sorted Ar

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

haobowd 2019-08-19 11:46 評論0 收藏0
leetcode刷題記錄-【26 Remove Duplicates from Sorted Ar

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

heartFollower 2019-08-19 11:46 評論0 收藏0
Leetcode 27 Remove Element

摘要：同時我們將這個元素賦值給，這樣就可以保證，不等于的個元素完美占據數組的前個位置。方法二當我們遇到和等于值的元素的時候，我們將數組尾端的元素和此元素交換位置。之后減少一位遍歷長度。同時在下次遍歷中，我們會重新檢查新過來的元素。題目介紹要求輸入：給定數組nums[]，數字val要求輸出：數組中不等于val的元素個數n，同時要求不等于數字val的n個元素放置在數組的前n個位置（不要求順序...

_ipo 2019-08-15 13:34 評論0 收藏0
13. 羅馬數字轉整數-----leetcode刷題（python解題）

摘要：題目羅馬數字包含以下七種字符，，，，，和。字符數值例如，羅馬數字寫做，即為兩個并列的。通常情況下，羅馬數字中小的數字在大的數字的右邊。同樣地，數字表示為。給定一個羅馬數字，將其轉換成整數。 [TOC] 題目羅馬數字包含以下七種字符: I， V， X， L，C，D 和 M。字符數值 I 1 V 5 X ...

Gu_Yan 2019-07-31 10:38 評論0 收藏0