LeetCode中怎樣刪除排序數組中的重復項

LeetCode中怎樣刪除排序數組中的重復項

在LeetCode中，刪除排序數組中的重復項是一個常見的算法問題。這個問題要求我們在一個已經排序的數組中，刪除所有重復的元素，并返回新數組的長度。本文將詳細介紹如何解決這個問題，并提供相應的代碼示例。

問題描述

給定一個排序數組 nums，你需要原地刪除重復出現的元素，使得每個元素只出現一次，并返回新的長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成。

示例

輸入: nums = [1,1,2]
輸出: 2, nums = [1,2]
解釋: 函數應該返回新的長度 2，并且原數組 nums 的前兩個元素被修改為 1, 2。你不需要考慮數組中超出新長度后面的元素。

解題思路

由于數組是已經排序的，因此重復的元素一定是相鄰的。我們可以利用這一特性，通過雙指針的方法來解決這個問題。

雙指針法

1. 初始化指針：我們使用兩個指針 i 和 j，其中 i 是慢指針，j 是快指針。初始時，i 指向數組的第一個元素，j 指向第二個元素。

2. 遍歷數組：我們遍歷數組，當 nums[j] 與 nums[i] 不相等時，說明 nums[j] 是一個新的元素，我們將 nums[j] 的值賦給 nums[i+1]，然后 i 向前移動一位。

3. 返回結果：遍歷結束后，i+1 就是新數組的長度。

代碼實現

def removeDuplicates(nums):
    if not nums:
        return 0
    
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    
    return i + 1

代碼解釋

• 判斷數組是否為空：如果數組為空，直接返回 0。
• 初始化指針：i 初始化為 0，j 從 1 開始遍歷數組。
• 遍歷數組：當 nums[j] 不等于 nums[i] 時，將 nums[j] 的值賦給 nums[i+1]，然后 i 向前移動一位。
• 返回結果：遍歷結束后，i+1 就是新數組的長度。

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。我們只需要遍歷一次數組。
• 空間復雜度：O(1)，我們只使用了常數級別的額外空間。

總結

通過雙指針法，我們可以高效地刪除排序數組中的重復項，并且不需要額外的空間。這種方法不僅適用于LeetCode中的這個問題，也可以應用于其他類似的場景。希望本文能幫助你更好地理解和解決這個問題。