iT邦幫忙

0

[用 Python 解 LeetCode] (003) 80. Remove Duplicates from Sorted Array II

  • 分享至 

  • xImage
  •  

題幹懶人包

給定一個排列好的列表,將它整理成重複項最多出現兩次,比方說以下

[1,1,1,2,2,3] -> [1,1,2,2,3, ...]

最後回傳整理完成的數量,比方說上面會回傳 5 (1, 1, 2, 2, 3)。

最後以下幾點要注意

  1. 只能修改該數組,利用的空間複雜度最多為1(意思就是不能創建新的數組append值)

  2. 不用管超過回傳值以後nums的值

"""
比方說輸入的 nums = [0,0,1,1,1,1,2,3,3]
那最後回傳值要等於7,且 nums[:7] 要等於 [0,0,1,1,2,3,3]
"""

解法

用 head 紀錄當前元素,tmp紀錄元素重複幾次,接下來迴圈開始比較當前值與下一個值,

  1. 如果當前元素不等於遍歷到的數值,head += 1 ,並在下標為 head 的地方存放元素,並將tmp設定成0(因為tmp要重置不然之後無法紀錄重複有無發生)
  2. 當元素相同時,優先查看 tmp 是否為0,如果是的話代表該元素上一個沒出現過,head += 1 ,並在下標為 head 的地方存放元素,並將 tmp += 1

最後返回 head + 1 (因為head是下標值,非長度)

def removeDuplicates(self, nums) -> int:
        head = 0
        tmp = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[head]:
                head += 1
                tmp = 0
                nums[head] = nums[i]
            else:
                if tmp == 0:
                    head += 1
                    tmp += 1
                    nums[head] = nums[i]
        return head + 1

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言