题目描述如下
给定一个排序数组,你需要在删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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)
可以看到,其实思路非常简单,如果我们从顺序遍历的话,删除某个元素会影响下一个序列,再进行处理其实是有点绕的,而逆序的方法完美解决了这个问题。
不难想,但是我在思索到正序删除不好处理序列号之后就放弃了,可见还是见识太少了,以后还是应该多思考下啊。
网友评论