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)了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。