LeetCode_26_删除排序數組中的重複項

文章目錄

• 題目
• 思路：雙指針

題目

給定一個排序數組，你需要在 原地 删除重複出現的元素，使得每個元素隻出現一次，傳回移除後數組的新長度。

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

思路：雙指針

分析：

拿到題首先分析一下，這是一個已經排好序數組，需要删除數組中重複的元素，而且是就地删除，通過下面的題幹知道，所謂的删除并不是将重複的元素如下：

不需要考慮數組中新長度後面的元素，就是說新的數組并不需要删除重複的元素，隻需要把前面重複的元素覆寫掉，然後傳回新數組的大小，程式就會根據傳回的數組大小去數組的前n個位置取元素。

使用雙指針，a指針始終指向目前新數組的最後一個元素，使用b指針周遊數組，一旦發現

nums[b]>nums[a]

就代表着找到下一個元素，此時将nums[b]複制給nums[++a]，如此循環至數組完畢！

程式：

int removeDuplicates(int* nums, int numsSize){
    unsigned int a,b;
    if( numsSize<2 ){//判斷，如果小于兩個元素，直接傳回，沒有重複
        return numsSize;
    }
    /* 開始周遊 */
    for( a=0,b=0; b<numsSize; b++ ){//無論發生什麼，b指針都更新
        if( nums[b]>nums[a] ){//發現新元素
            a++;
            nums[a] = nums[b];
        }
    }
    a++;//數組下标包含了0，是以傳回的時候+1，就是數組元素的個數。
    return a;
}
           

運作結果：