问题
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def get_dropped_count(nums: list):
if not nums:
return 0
# 直接从第二个元素开始
slow_idx = fast_idx = 1
last_fast_data = nums[0]
while fast_idx < len(nums):
# 判断和上一个元素比是否相同
if nums[fast_idx] != last_fast_data:
# 找到一个不重复的，把slow_idx位置的值置为fast_idx查到的不重复的值
nums[slow_idx] = nums[fast_idx]
# slow_idx 向前走一步
slow_idx += 1
# 更新上一个 fast 值
last_fast_data = nums[fast_idx]
# fast_idx 继续向前探路
fast_idx += 1
print(nums)
return slow_idx
if __name__ == '__main__':
data = [0, 1, 1, 2, 3, 5, 6, 6, 9, 9]
print(get_dropped_count(data)) # 7
笔者还看到有这样一个解法，执行时间更少一些：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_dropped_count(nums: list):
if not nums:
return 0
slow_idx = fast_idx = 0
while fast_idx < len(nums):
# 判断和最近一个已去重元素比是否相同
if nums[fast_idx] != nums[slow_idx]:
# 找到一个不重复的，
# slow_idx 向前走一步
slow_idx += 1
# 把slow_idx位置的值置为fast_idx查到的不重复的值
nums[slow_idx] = nums[fast_idx]
# fast_idx 继续向前探路
fast_idx += 1
print(nums)
return slow_idx + 1
if __name__ == '__main__':
data = [0, 1, 1, 2, 3, 5, 6, 6, 9, 9]
print(get_dropped_count(data)) # [0, 1, 2, 3, 5, 6, 9, 6, 9] 7
这种解法和前一个解法相比，判断 fast 指针是否找到了重复的元素的方法不同，slow 指针的含义也不同。
前者：如果当前元素和上一个元素不同，则该元素首次出现（因为有序），则可以把 slow 指针位置的值置为该值。一次循环后，slow 指针指向下一个不重复的值。
后者：如果当前元素和去重过的最后一个元素不同，则该元素首次出现（因为有序），则可以让 slow 指针前进一步，再把 slow 指针位置的值置为该值。一次循环后，slow 指针指向最后一个不重复的值。
不用指针
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-c-8/
class Solution {
public int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return 1;
int result=1;
for(int i=0; i!=nums.size()-1; i++)
{
if(nums[i] != nums[i+1])
{
nums[result++]=nums[i+1];
}
}
return result;
}
};
用 Python 实现如下：
def get_dropped_count(nums: list):
length = len(nums)
if length < 2:
return length
result = 1
for i in range(length - 1):
if nums[i] != nums[i + 1]:
nums[result] = nums[i + 1]
result += 1
print(nums)
return result
if __name__ == '__main__':
data = [0, 1, 1, 2, 3, 5, 6, 6, 9]
print(get_dropped_count(data)) # [0, 1, 2, 3, 5, 6, 9, 6, 9] 7