题目描述
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例：
输入：nums = [1,1,2]
输出：2
说明：
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
解题思路
1. 双指针法
首先注意数组是有序的，那么重复的元素一定会相邻。 要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。
设置双指针，比较两个指针，i是慢指针，在后面，而 j是快指针，在前面。 只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。
当我们遇到 nums[j]≠nums[i]时，跳过重复项的运行已经结束，因此我们必须把它nums[j]的值复制到 nums[i+1] 。
- 时间复杂度：O(n)，假设数组的长度是 n，那么 i 和 j分别最多遍历 n 步
- 空间复杂度：O(1)
Java
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
Python
用两个指针，指向第一个和第二个元素，如果他们相等，删除第二个元素。指针还指向原来的位置，继续比较。不等的话，两个指针位置都加一。遍历结束即可。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
pre,cur=0,1
while cur<len(nums):
if nums[pre]==nums[cur]:
nums.pop(cur)
else:
pre,cur=pre+1,cur+1
return len(nums)
2. 反向遍历法
从nums的最后一个开始遍历, 然后与前一个进行对比， 果相等, 则删除该位置的数 ， 不等, 则继续往前遍历 。
- 时间复杂度：O(n)，假设数组的长度是 n，那么 i 和 j分别最多遍历 n 步
- 空间复杂度：O(1)
Python
def removeDuplicates(nums):
for num_index in range(len(nums)-1, 0, -1):
if nums[num_index] == nums[num_index-1]:
nums.pop(num_index)
return len(nums)
Go
func removeDuplicates(nums []int) int {
for i:=len(nums)-1; i>0; i-- {
if nums[i] == nums[i-1] {
nums = append(nums[:i], nums[i+1:]...)
}
}
return len(nums)
}
总结
用for循环就会衍生出一个问题: 在遍历列表/数组/切片等的过程中, 此时该列表/数组/切片等的长度会发生变化.
可以改用while循环进行解答 。但是注意的是正向遍历有影响, 可以反向遍历。
需要注意 Go 语言比 Python 消耗的内存和时间都小很多。
数组的删除，有位置的动态变化，但是不能使用额外的空间。
另，如何实现无序数组的重复元素删除呢？
Reference
[1.] https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-fen/
[2.] https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-by-/
[3.] https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shuang-zhi-zhen-shan-chu-zhong-fu-xiang-dai-you-hu/
