這題是在一個已排序的整數組 nums ,移除多餘的重複元素,讓每個元素最多出現兩次,且保持原有的順序,最後返回處理後的長度 k,要保證前 k 個元素都符合條件。
理解題目:
目標是不用額外的空間,修改輸入數組,每個數字最多只能出現兩次,且要保持元素的相對順序,返回一個整數 k,表經過修改後,符合條件的數組長度。
分析:
因為數組已排好順序,所以重複的數字一定是相鄰的,可以逐一遍歷數組,記錄每個數字的出現次數,次數大於2就跳過那個數。
技巧:
用兩個指針,一個指針 i 遍歷整個數組,另一個指針 j 追蹤有效數字位置,就是用來修改數組的內容,確認最多保留兩次(每個數字),遍歷到一個新的數或出現的次數少於等於 2 ,把那個數字放到 j 指的位置,再增加 j。
步驟:
遍歷整個 nums 數組,用變量記錄當前數字出現的次數,如果當前數字出現次數不超過兩次,就把它加到結果數組中,最後返回有效數組的長度 k。
先初始化指針,可以直接從第 2 個元素開始處理,因為前兩個元素不管怎樣都能保留,然後確認邊界條件,如果數組長度小於等於 2,那就直接返回數組長度,因為沒必要做任何操作,再遍歷數組,修改,依次查看每個元素,在需要的時後修改數組。
(用雙指針方法來解決問題)
程式碼:
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#如果數組長度小於等於 2,直接返回數組長度,(每個元素最多出現兩次)
if len(nums) <= 2:
return len(nums)
#j 用來指向修改後數組中的位置,從索引 2 開始
j = 2
#從索引 2 開始遍歷數組,因為要保留前兩個元素
for i in range(2, len(nums)):
# 如果當前元素 nums[i] 跟 nums[j-2] 不同,表可保留這個元素
if nums[i] != nums[j-2]:
nums[j] = nums[i] # 把當前元素放到索引 j 的位置
j += 1 # 更新 j 的位置
return j # 返回有效的數組長度
解釋:
初始情況,直接保留數組的前兩個元素,因為它們無論如何都是有效的,雙指針遍歷,從第三個元素開始,當前元素跟前兩個元素不同,把它保留到新的位置,結束條件,遍歷完,j 指針的值就是處理後數組的有效長度。
時間複雜度,O(n), n 是數組的長度,因為只遍歷了一次數組。
空間複雜度,O(1),因為只用了常數的額外空間。
心得:
這題考對雙指針技術的應用,這種能力對處理有序數組和數列很常見,尤其是在需要 "就地" 改數組的問題,主要是要熟悉 API ,學怎麼在不分配額外空間的情況,做數組的原地操作,對效能優化有很大的用處,一開始從簡單的問題下手,熟悉基礎概念,然後之後處理類似的高階問題會比較不會卡關,還能提升邏輯思考的能力,增強對數據結構和演算法的理解力。