LEETCODE刷題記錄【27 Remove Element】

馬龍駒發(fā)布于2019-08-19 11:45 / 3171人閱讀

摘要：復(fù)雜度分析時(shí)間復(fù)雜度遍歷次空間復(fù)雜度還有沒有優(yōu)化空間方法在某些特定場(chǎng)景下會(huì)進(jìn)行不必要的復(fù)制操作，影響性能。注意尾部的元素有可能是需要剔除的，所以，下一輪循環(huán)要從當(dāng)前索引重新開始。

給定一個(gè)數(shù)組 nums?和一個(gè)值 val，你需要原地移除所有數(shù)值等于?val?的元素，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

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

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;
}

基礎(chǔ)知識(shí)查漏補(bǔ)缺：
1.Java數(shù)組的聲明、初始化和使用
遇到了一個(gè)問題，新的數(shù)組需要聲明和初始化，但是新數(shù)組的長(zhǎng)度還不知道，怎么初始化。
考慮使用ArrayList
2.ArrayList的聲明和使用
3.靜態(tài)方法中調(diào)用非靜態(tài)方法的限制

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

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

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;
}

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

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

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.在循環(huán)里，把nums.length作為了固定長(zhǎng)度，會(huì)導(dǎo)致所有元素都被遍歷，實(shí)際上被替換到前面的元素不需要被遍歷，導(dǎo)致了bug
2.在使用i--時(shí)，考慮如果數(shù)組前幾個(gè)元素都是需要被剔除的元素，會(huì)不會(huì)導(dǎo)致index為負(fù)，導(dǎo)致溢出。經(jīng)過分析和實(shí)驗(yàn)不會(huì)，因?yàn)槊看窝h(huán)結(jié)束i都要++

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

總結(jié)：
1.學(xué)會(huì)的新方法，雙指針法
2.如果沒有普遍的優(yōu)化方法，那么就考慮業(yè)務(wù)場(chǎng)景的特點(diǎn)，比如方法三，針對(duì)某些特殊場(chǎng)景提出優(yōu)化空間。