每日一道算法：删除排序數組中的重複項

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

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

示例1：

輸入:給定數組 nums = [1,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。

你不需要考慮數組中超出新長度後面的元素。

說明：

為什麼傳回數值是整數，但輸出的答案是數組呢?

請注意，輸入數組是以“引用”方式傳遞的，這意味着在函數裡修改輸入數組對于調用者是可見的。

解法一：雙指針法

相關标簽

* 數組
* 雙指針           

思路分析：

1、數組完成排序後，我們可以放置兩個指針i和j，其中i是慢指針，而j是快指針。隻要nums[i]=nums[j]，我們就增加j以跳過重複項。

2、當我們遇到nums[j]!=nums[i]時，跳過重複項的運作已經結束，是以我們必須把它（nums[j]）的值複制到nums[i+1]。然後遞增i，接着我們将再次重複相同的過程，直到j到達數組的末尾為止。

PHP代碼實作：

/**
 * @param Integer[] $nums
 * @return Integer
 */
function removeDuplicates(&$nums) {
    if(count($nums)==0){
        return 0;
    }
    $slow = 0;//慢指針
    for($fast=1;$fast<count($nums);$fast++){//快指針
        if($nums[$slow] != $nums[$fast]){
            $slow++;
            $nums[$slow] = $nums[$fast];//把快指針的值指派給結束重複項慢指針+1
        }
    }
    return $slow+1;//數量比指針多1
}           

使用：
$nums = [1,2,3,4,5,6,7,8,8,8,9,9,9];
var_dump(removeDuplicates($nums));           

複雜度分析：

時間複雜度： O(n)
假設數組的長度是n，那麼i和j分别最多周遊n步
空間複雜度： O(1)           

解題關鍵

一定要審題清楚，這個在做算法題非常重要（我就在做這題時犯了這個大忌）

審題關鍵點：

1、給定一個排序數組，表示是已經排好序的數組

2、原地修改，即要求空間複雜度為O(1)

3、你不需要考慮數組中超出新長度後面的元素，即表示不用删除重複的元素，可以把重複的元素移動到最後即可

github

以後每次題解都會上傳到這個項目 LeetCode_PHP：https://github.com/zhangdejian/LeetCode_PHP

題目來源

力扣（LeetCode）： https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/