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

題目：

26. 刪除排序數(shù)組中的重復(fù)項 -> Link

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

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

示例 1:

給定數(shù)組 nums = [1,1,2], 

函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。 

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

示例 2:

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

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

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

說明:

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

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

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

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

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

題目分析

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

如果不注意題干的話，這個題很容易可以使用Set或者Hash來去重。但是使用Set和Hash都會開辟新的內(nèi)存空間。增加空間復(fù)雜度，這里可以用到雙指針法。

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

復(fù)雜度分析

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

Java

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

Swift

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

JavaScript

var removeDuplicates = function(nums) {
    
    if (nums === 'undefined' || nums.length === 0) {
        return 0
    }
    var i = 1;
    for (var j = 1; j < nums.length; j++) {
        
        if (nums[j] != nums[j - 1]) {
            nums[i] = nums[j];
            i++;
        }
        
    }
    return i;
    
};

相關(guān)類似題目
27.移除元素