Tags: Two Pointer,雙指針,java,swift,javascript

題目

27. 移除元素 -> Link

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

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

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

示例 1:

給定 nums = [3,2,2,3], val = 3,

函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。

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

示例 2:

給定 nums = [0,1,2,2,3,0,4,2], val = 2,

函數(shù)應(yīng)該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。

注意這五個元素可為任意順序。

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

說明:

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

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

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

// nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);

// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中該長度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

題目分析

本題中涉及到了原地的感念，是一種使用小的，固定數(shù)量的額外之空間來轉(zhuǎn)換資料的算法。當算法執(zhí)行時，輸入的資料通常會被要輸出的部份覆蓋掉。

這一題的跟題號#26的思路很一致，用雙指針法。

1. 首先判斷傳入數(shù)組不為空且長度大于一；
2. 定義新的數(shù)組的長度newLength，從0開始，慢指針；
3. 遍歷數(shù)組,定義快指針i；
4. 當num[i] == val，慢指針newLength不變，快指針i+1。跳過目標val項。
5. 當num[i] != val, 慢指針newLength+1，快指針i+1，nums[newLength] = nums[i]。
6. 重復相同過程直到循環(huán)結(jié)束。

復雜度分析

• 時間復雜度：O(n)， 假設(shè)數(shù)組總共有 n 個元素，i 和 j 至少遍歷 2n 步。
• 空間復雜度：O(1)。

Java

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int newLength = 0;
            for (int i = 0; i < nums.length; i ++) {
                    if (nums[i] != val) {
                nums[newLength] = nums[i];
                            newLength ++;
                    }
            }
            return newLength;
    }
}

Swift

class Solution {
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        guard nums.count > 0 else {
            return 0
        }
        var newLength = 0;
        for idx in 0 ..< nums.count {
            
            if nums[idx] != val {
                nums[newLength] = nums[idx]
                newLength += 1
            }
        }
        return newLength
    }
}

JavaScript

var removeElement = function(nums, val) {
    if (nums === 'undefined' || nums.length === 0) {
        return 0
    }
    var newLength = 0;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[newLength] = nums[i];
            newLength++;
        }
    }
    return newLength;
};

相關(guān)類似題目
26. 刪除排序數(shù)組中的重復項