题目:
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 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。 你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); } 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
解题:
方法一：
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)
从前两个数开始，相邻的两个对比，重复就删除后面一个数
上述这种方法的缺点是，要是输入nums = [4,0,1,1,1,2,2,3,3,4]这样的列表，就不能正确的输出结果，该算法要求列表中的数把重复的放在一起。当然题目已经排序好了。
方法二：
class Solution: def removeDuplicates(self, nums: List[int]) -> int: nums[:] = list(sorted(set(nums))) return len(nums)
利用集合set的性质，相同元素只能存在一个。再转化为list，中途还排序了。nums[:]是对列表nums的内容进行修改。list(sorted(set(nums)))是新开辟内存空间，然后赋值给nums，必须用nums[:]修改。nums= list(sorted(set(nums))),如果是只写nums,也就是nums给的新的内存空间，就不能对原列表修改了。
方法三(lc官方解法)：
class Solution: def removeDuplicates(self, nums: List[int]) -> int: if len(nums) == 0: return 0 i = 0 for j in range(1,len(nums)):#从0和1开始都行，因为第0个肯定是不同的一般就写从1开始了。 if nums[j] != nums[i]: i+=1 nums[i] = nums[j] # nums[:] = nums[:i+1] 题目中说了 你不需要考虑数组中超出新长度后面的元素。因此可以不加这句话 return i + 1
双指针法，i是慢指针，j是快指针。只要两指针指向的内容不同，就给i指向的内容。那么前i+1个数就是不重复的。
或者换种写法的风格:
class Solution: def removeDuplicates(self, nums: List[int]) -> int: slow=0 fast=0 while fast<len(nums): if nums[fast]!=nums[slow]: slow+=1 nums[slow]=nums[fast] fast+=1 return slow+1
但是注意，这种情况就不行了。 slow+1放后面挪动一下，就不行了。
class Solution: def removeDuplicates(self, nums: List[int]) -> int: slow = 0 fast = 1 while fast<len(nums): if nums[slow]!=nums[fast]: slow+=1 nums[slow]=nums[fast] # print(slow,fast,nums) fast+=1 return slow+1
比如输入的是[0,0,1,1,1,2,2,3,3,4],打印一下可以发现
1 1 [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 2 2 [0, 1, 1, 1, 1, 2, 2, 3, 3, 4] 2 3 [0, 1, 1, 1, 1, 2, 2, 3, 3, 4] 2 4 [0, 1, 1, 1, 1, 2, 2, 3, 3, 4] 3 5 [0, 1, 2, 1, 1, 2, 2, 3, 3, 4] 4 6 [0, 1, 2, 2, 1, 2, 2, 3, 3, 4] 5 7 [0, 1, 2, 2, 3, 2, 2, 3, 3, 4] 6 8 [0, 1, 2, 2, 3, 3, 2, 3, 3, 4] 7 9 [0, 1, 2, 2, 3, 3, 4, 3, 3, 4]
3 5 [0, 1, 2, *1*, 1, *2*, 2, 3, 3, 4]
加星的这两个在比较，于是出现了问题，我们要*1*前面的2和后面的做比较。而不是把要置换的东西和后面做比较。
因此要先比较完，然后slow+=1，把后面的一个给置换掉。
