26. 刪除有序數組中的重復項(remove-duplicates-from-sorted-array)

給你一個 非嚴格遞增排列 的數組 nums ，請你** 原地** 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除后數組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數。

考慮 nums 的唯一元素的數量為 k ，你需要做以下事情確保你的題解可以被通過：

• 更改數組 nums ，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現的順序排列。nums 的其余元素與 nums 的大小不重要。
• 返回 k 。

判題標準:

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

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 。不需要考慮數組中超出新長度后面的元素。

提示：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按 非嚴格遞增 排列

首先注意數組是有序的，那么重復的元素一定會相鄰。

要求刪除重復元素，實際上就是將不重復的元素移到數組的左側。

考慮用 2 個指針，一個在前記作 p，一個在后記作 q，算法流程如下：

1.比較 p 和 q 位置的元素是否相等。

如果相等，q 后移 1 位
如果不相等，將 q 位置的元素復制到 p+1 位置上，p 后移一位，q 后移 1 位
重復上述過程，直到 q 等于數組長度。

返回 p + 1，即為新數組長度。

p	q
0	0	1	1	1	2	2	3	3	4

java代碼

 public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int p = 0;int q = 1;while(q < nums.length){if(nums[p] != nums[q]){nums[p + 1] = nums[q];p++;}q++;}return p + 1;
}

golang代碼

func removeDuplicates(nums []int) int {n := len(nums)if n == 0 {return 0}slow := 1for fast := 1;fast < n;fast++ {if nums[fast] != nums[fast-1] {nums[slow] = nums[fast]slow++}}return slow
}