Python里面如何从一道简单算法题里面解释什么叫做 O(1)

这期内容当中小编将会给大家带来有关Python里面如何从一道简单算法题里面解释什么叫做 O(1)，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

今天有同学在粉丝群里面问了一个算法题：

对话中的题目如下：

题目要求从一个有序数组 nums 中，原地删除重复出现的元素，使得每个元素只出现一次。返回删除后数组的长度。不能使用额外的数组空间，使用  O(1)空间复杂度。

这个同学之所以做错了，是因为他没有理解什么叫做  O(1)空间复杂度。他在第3行实际上生成了一个新的列表。这个列表的长度取决于原来列表的长度，原来列表不重复的元素越多，这个新的列表也就越长，所以它的空间复杂度是  O(n)。而且题目要求“原地”修改原来的列表，而不是生成新的列表。

我们先说说什么叫做O(1)空间复杂度。它不是指只能申请1个变量，而是指你额外申请的变量数量是恒定的，不会根据输入列表元素的数量而变化。所以，即使你申请1万个变量，但无论输入的原列表有1个元素还是1亿个元素，你始终只使用这1万个变量，那么也可以说空间复杂度为  O(1)。

再来说说什么叫做原地修改。这就是说，你直接修改输入的列表，不额外使用新的列表。我们知道，在 Python  里面，向列表里面添加一个元素使用xxx.append(yy)，从列表里面根据索引删除一个元素xxx.pop(index)，都是原地修改。

回到这道题目，这道题属于 LeetCode 上面简单级别的题目，如果要应聘好一些的互联网公司，这种题目应该能做到信手拈来。

这道题的关键，在于原来的列表是有序列表，所以重复的数字一定是连在一起的。因此，  我们只需要逐一检查当前元素跟上一个元素是否相同，如果相同，就移除当前元素，如果不同，就检查下一个元素。

因此，我们来写代码：

class Solution:     def removeDuplicates(self, nums):         if not nums:             return 0         last = None         index = 0         length = len(nums)         while index < length:             ele = nums[index]             if index == 0:                 last = ele                 index = 1             elif ele == last:                 length -= 1                 nums.pop(index)             else:                 last = ele                 index += 1         return length

运行效果如下图所示：

需要注意的是，这道题的时间复杂度是  O(n)，因为从列表里面根据索引删除元素的时候，后面的元素会依次向前移动一位。一般来说，时间复杂度和空间复杂度是不能兼得的。你可以用空间换时间，也可能用时间换空间，但是很难做到同时又不占空间又不占时间。

上述就是小编为大家分享的Python里面如何从一道简单算法题里面解释什么叫做 O(1)了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。