【初級演算法】刪除排序數組中的重複項

• 2022 年 6 月 1 日
• 筆記
• 雙指針, 演算法

刪除排序數組中的重複項

給你一個 升序排列 的數組 nums ，請你 原地 刪除重複出現的元素，使每個元素 只出現一次 ，返回刪除後數組的新長度。元素的 相對順序 應該保持 一致 。

由於在某些語言中不能改變數組的長度，所以必須將結果放在數組nums的第一部分。更規範地說，如果在刪除重複項之後有 k 個元素，那麼 nums 的前 k 個元素應該保存最終結果。

將最終結果插入 nums 的前 k 個位置後返回 k 。

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

判題標準:

系統會用下面的程式碼來測試你的題解:

int[] nums = [...]; // 輸入數組
int[] expectedNums = [...]; // 長度正確的期望答案

int k = removeDuplicates(nums); // 調用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有斷言都通過，那麼您的題解將被 通過。

示例 1：

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

示例 2：

**輸入：**nums = [0,0,1,1,1,2,2,3,3,4]
**輸出：**5, nums = [0,1,2,3,4]
**解釋：**函數應該返回新的長度 **`5`** ， 並且原數組 _nums_ 的前五個元素被修改為 **`0`**, **`1`**, **`2`**, **`3`**, **`4`** 。不需要考慮數組中超出新長度後面的元素。

提示：

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 升序 排列

題解

因為數組是排序的，只要是相同的肯定是挨著的，我們只需要遍歷所有數組，然後前後兩兩比較，如果有相同的就把後面的給刪除。

1，雙指針解決

使用兩個指針，右指針始終往右移動，

• 如果右指針指向的值等於左指針指向的值，左指針不動。
• 如果右指針指向的值不等於左指針指向的值，那麼左指針往右移一步，然後再把右指針指向的值賦給左指針。

//雙指針解決
public int removeDuplicates(int[] A) {
    //邊界條件判斷
    if (A == null || A.length == 0)
        return 0;
    int left = 0;
    for (int right = 1; right < A.length; right++)
        //如果左指針和右指針指向的值一樣，說明有重複的，
        //這個時候，左指針不動，右指針繼續往右移。如果他倆
        //指向的值不一樣就把右指針指向的值往前挪
        if (A[left] != A[right])
            A[++left] = A[right];
    return ++left;
}

或者還可以換一種解法，其實原理都是一樣的。

public int removeDuplicates(int[] A) {
    int count = 0;//重複的數字個數
    for (int right = 1; right < A.length; right++) {
        if (A[right] == A[right - 1]) {
            //如果有重複的，count要加1
            count++;
        } else {
            //如果沒有重複，後面的就往前挪
            A[right - count] = A[right];
        }
    }
    //數組的長度減去重複的個數
    return A.length - count;
}