[[396914]]

今天有同學在粉絲群里面問了一個算法題：

對話中的題目如下：

題目要求從一個有序數(shù)組 nums 中，原地刪除重復出現(xiàn)的元素，使得每個元素只出現(xiàn)一次。返回刪除后數(shù)組的長度。不能使用額外的數(shù)組空間，使用 O(1)空間復雜度。

這個同學之所以做錯了，是因為他沒有理解什么叫做 O(1)空間復雜度。他在第3行實際上生成了一個新的列表。這個列表的長度取決于原來列表的長度，原來列表不重復的元素越多，這個新的列表也就越長，所以它的空間復雜度是 O(n)。而且題目要求“原地”修改原來的列表，而不是生成新的列表。

我們先說說什么叫做O(1)空間復雜度。它不是指只能申請1個變量，而是指你額外申請的變量數(shù)量是恒定的，不會根據(jù)輸入列表元素的數(shù)量而變化。所以，即使你申請1萬個變量，但無論輸入的原列表有1個元素還是1億個元素，你始終只使用這1萬個變量，那么也可以說空間復雜度為 O(1)。

再來說說什么叫做原地修改。這就是說，你直接修改輸入的列表，不額外使用新的列表。我們知道，在 Python 里面，向列表里面添加一個元素使用xxx.append(yy)，從列表里面根據(jù)索引刪除一個元素xxx.pop(index)，都是原地修改。

回到這道題目，這道題屬于 LeetCode 上面簡單級別的題目，如果要應聘好一些的互聯(lián)網(wǎng)公司，這種題目應該能做到信手拈來。

這道題的關鍵，在于原來的列表是有序列表，所以重復的數(shù)字一定是連在一起的。因此， 我們只需要逐一檢查當前元素跟上一個元素是否相同，如果相同，就移除當前元素，如果不同，就檢查下一個元素。

因此，我們來寫代碼：

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)，因為從列表里面根據(jù)索引刪除元素的時候，后面的元素會依次向前移動一位。一般來說，時間復雜度和空間復雜度是不能兼得的。你可以用空間換時間，也可能用時間換空間，但是很難做到同時又不占空間又不占時間。

本文轉(zhuǎn)載自微信公眾號「未聞Code」，可以通過以下二維碼關注。轉(zhuǎn)載本文請聯(lián)系未聞Code公眾號。