LeetCode 26 快慢指针

题目描述如下

给定一个排序数组，你需要在删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

举几个例子

[1,1,2]-->[1,2...]，返回2
[1,2,3,3,5]-->[1,2,3,5,..]，返回4
对于数组超出返回值序列之外的元素如何排列是不需要考虑的。

方法一：

没错，每次拿到题目总是想投机取巧，可能这就是算法能力那么垃圾的原因吧，不要学我。
看到这个题目不就是删除重复元素么，于是我首先想到了使用“set”函数，于是两句话的代买就这样出来了

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        a = list(set(nums))
        return a

然后报错了，仔细审题才发现，给定的是排序数组，那么返回的也是排序数组咯，这个倒是很简单，使用“sorted”处理一下就行；还有很重要的一点，不能使用额外的数组空间。这是一个相当大的限制，不能新创建一个数组让我感觉有点麻烦，甚至觉得投机取巧的方法不成了。直到后来看到评论区大神的代码：

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
    nums[:] = sorted(list(set(nums)))
    return len(nums)

没错，就多了一小步而已，然而我当时就是觉得不可行，，，可能这就是蔡鸡吧。

方法二：

当然，上面是为了搞笑的，由于不能创建一个新数组，快慢指针是很多人都能想到的方法。简单的介绍一下快慢指针，快慢指针其实就是字面上的意思，代表的是指针前进的步数，速度不同因而得名快慢指针。很经典的快慢指针的应用如：判断单链表是否循环，寻找有序链表中位数等。
在本题中，只要使得快指针指向重复元素的最后一个，和慢指针进行交换即可，代码如下：

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
    slow = 0
    fast = 0
    n = len(nums)
    while fast < n:
        while fast < n - 1 and nums[fast] == nums[fast+1]:
            fast += 1
        nums[slow] = nums[fast]
        slow += 1
        fast += 1
    return slow 

方法三

自古评论出大神，在评论区又遇到了个四行的逆遍历的算法，先贴上再分析：

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
    for i in range(len(nums)-1, 0, -1):
        if nums[i] == nums[i-1]: 
            nums.pop(i)
    return len(nums)

可以看到，其实思路非常简单，如果我们从顺序遍历的话，删除某个元素会影响下一个序列，再进行处理其实是有点绕的，而逆序的方法完美解决了这个问题。
不难想，但是我在思索到正序删除不好处理序列号之后就放弃了，可见还是见识太少了，以后还是应该多思考下啊。