移除元素Java實(shí)現(xiàn)方式

更新時間：2024年04月10日 10:50:06 作者：嘩嘩的世界

這篇文章主要介紹了移除元素Java實(shí)現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

題意

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

不要使用額外的數(shù)組空間，你必須僅使用額外空間并原地修改數(shù)組。

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

難度

簡單

說明

為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢?

請注意，輸入數(shù)組是以「引用」方式傳遞的，這意味著在方法里修改輸入數(shù)組對于調(diào)用者是可見的。

你可以想象內(nèi)部操作如下：

// nums 是以“引用”方式傳遞的。也就是說，不對實(shí)參作任何拷貝
int len = removeElement(nums, val);
 
// 在方法里修改輸入數(shù)組對于調(diào)用者是可見的。
// 根據(jù)你的方法返回的長度, 它會打印出數(shù)組中 該長度范圍內(nèi) 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例

輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：方法應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。例如，方法返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,3,0,4]
解釋：方法應(yīng)該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮數(shù)組中超出新長度后面的元素。

分析

看看本題的關(guān)鍵詞：原地、、返回移除后數(shù)組的新長度。

如果忽略原地、這兩個條件，我們可以很快寫出一個不錯的題解。

/**
 * @ClAssName RemoveElement
 * @Description TOOO
 * @Author woshi是神仙
 * @Date 2024/4/9 10:{MINUTE}
 */
public class RemoveElement {
 
    public static void main(String[] args) {
        //測試
        int[] nums =  new int[]{3 ,2 ,2 ,3 };
        int val = 3;
        System.out.println(removeElement(nums, val));
 
    }
 
    /**
     * 刪除數(shù)組中給定的元素，并返回新數(shù)組長度
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement( int[] nums , int val){
        //初始化一個數(shù)組res，長度與nums相同，用于存儲移除目標(biāo)元素后的結(jié)果
        int[] res = new int[nums.length];
        //初始化一個指針 j ，用于標(biāo)記新數(shù)組索引位置，初始值為0
        int j = 0;
        //遍歷數(shù)組過濾目標(biāo)數(shù)
        for (int i = 0; i < nums.length; i++) {
            //判斷當(dāng)前元素是否等于目標(biāo)值，過濾
            if (nums[i] != val){
                res[j++] = nums[i];
            }
        }
        //過濾完，返回新數(shù)組的長度，定義了 j 指針實(shí)現(xiàn)的
        return  j ;
    }
}

Java 并不存在引用傳遞，只有值傳遞，數(shù)組是一種特殊的對象，傳遞的是對象在堆中的地址，所以在方法中修改數(shù)組的內(nèi)容是會影響到調(diào)用者的。

從上面的例子可以看到，i一直都大于等于j，所以我們完全可以利用nums[0 ~ i - 1]來存儲res的內(nèi)容，所以題解就有了。

    public static int removeElement2( int[] nums , int val){
        //初始化兩個指針 i 和 j ，都是從數(shù)組的起始位置0開始的
         int i = 0 , j = 0;
 
         //遍歷數(shù)組，i 用于遍歷數(shù)組 ， j 用于 指向下一個要更新的元素位置·
        for (; i < nums.length; i++) {
            //過濾掉目標(biāo)值
            if (nums[i] != val){
                //將當(dāng)前元素復(fù)制到 j 指向的位置
                nums[j++] = nums[i];
            }
        }
        //循環(huán)結(jié)束后，j就時新數(shù)組的長度，因?yàn)樗胁坏扔趘al的元素都被復(fù)制到了數(shù)組的里面了
        return  j;
    }

通過這種方式，所有等于 val 的元素都被“跳過”了，沒有被復(fù)制到數(shù)組的前端。遍歷結(jié)束后，j 的位置就是新數(shù)組的長度，因?yàn)樗赶蛄说谝粋€“空閑”的位置，也就是第一個沒有被復(fù)制過的元素的位置。這樣，我們就實(shí)現(xiàn)了在原地修改數(shù)組的目標(biāo)，并且返回了新數(shù)組的長度。

來看看題解效率：

只需要判斷是否等于目標(biāo)值即可，所以這道題的時間復(fù)雜度是，空間復(fù)雜度是，非常簡單，一兩分鐘就能輕松解決！

對本道題時操作數(shù)組的，可以換另外一種寫法。

 public static int removeElement3( int[] nums , int val){
        //如果數(shù)組為空，直接返回
        if (nums.length ==0){
            return 0 ;
        }
        //定義一個慢指針
        int i = 0;
        // j 為快指針 ，用來遍歷數(shù)組
        for (int j = 0; j < nums.length; j++) {
            //如果當(dāng)前元素不等于給定元素
            if (nums[j] != val){
                //將當(dāng)前元素復(fù)制到慢指針的位置
                nums[i] = nums[j];
                
                //移動慢指針
                i++;
            }
        }
        //返回不重復(fù)元素的個數(shù)。
        return  i;
    }