简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
一、写在前面
LeetCode 第八题 有效的括号 传输门：LeetCode008 : 有效的括号
今天给大家分享的是LeetCode 数组与字符串 第九题：删除排序数组中的重复项，为面试而生，期待你的加入。
二、今日题目
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。
你不需要考虑数组中超出新长度后面的元素。
三、 分析
这个题目的话，第一眼看上还是愣了一下，只能在原列表操作，而且额外空间复杂度得保证为O(1)。
不过仔细一想，也还比较好做，因为原列表已经有序，我们要做的就是把重复元素去除或者移到后面去，因为最后removeDuplicates函数的返回值是最长的无重复列表长度，就好像示例1中的，返回值就为2，打印的结果是修改后的列表的前两个元素[1,2]，接下来看看我的思路分析吧：
我的思路
图解算法
四、解题
- 我的方法：
时间复杂度：O(n)
空间复杂度：O(1),符合题意
# 我的方法 class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) if n<=0: # 长度小于或等于1 return 0 len_0 = 1 for i in range(1,n): # for循环向后遍历 if nums[i] != nums[i-1]: nums[len_0] = nums[i] # 数据替换 len_0 = len_0 + 1 # 指针后移 return len_0
- 提交结果
昨天第一次提交
今天又提交了几次
测试数据：161组
运行时间：44-152ms
击败人百分比:7.95-99.54%
- 最简单解法
利用set集合去除列表元素，直接改变原列表
时间复杂度：O(1)
空间复杂度：O(1)
class Solution(): def removeDuplicates(self,nums): """ :type nums: List[int] :rtype: int """ nums[:] = list(sorted(set(nums))) return len(nums)
- 提交结果
提交5次
测试数据：161组
运行时间：44-80ms
击败人百分比:22.34-99.54%
五、疑惑
首先，我今天确定了，讨论算法优秀，或者最优解，并不能靠提交结果来看，得从时间复杂度和空间复杂度以及实现难度上来看，后面算法刷题我也会注意这一点，多分析复杂度计算。
六、结语
不知不觉，一个多月过去了，和自己说一句加油吧，如果你和我一样还在坚持的话~
留一个问题：如果你在面试遇到这个题目，如何快速找出有序列表非重复元素？你会给出那种解答，直接说用set集合就可以去重还是语重心长的和HR讲思想？或者你会怎么解答这个问题？（留言给出你的答案吧~）
坚持 and 努力 ： 终有所获。
