處理這種需要就地修改且允許順序改變的陣列問題,雙指針(Two Pointers)是一個非常有效且常見的技巧。首先設置兩個指標i和k來遍歷陣列,i用來遍歷整個陣列,檢查每個元素nums[i]是否等於val。k用來指向下一個合格元素(即不等於val的元素)應該被寫入的位置。同時,k的最終值就是要回傳的合格元素總數。
接著,初始化k = 0(寫入位置,同時也是計數器)。
再來,使用i從頭到尾遍歷陣列。如果nums[i]不等於val(合格元素),將nums[i]的值複製到nums[k]的位置(nums[k] = nums[i]),然後,將寫入指標k向後移動一位(k++),準備接收下一個合格元素;如果nums[i]等於val(不合格元素),那就什麼都不做,因為只是要「跳過」或「移除」它。此時k保持不動,nums[i]的值會被後續的合格元素覆蓋。
遍歷結束後,k的值就是不等於val的元素的總數量,並且前k個元素已經被正確地排列。
複雜度分析
時間複雜度(Time Complexity):O(n)。這題只使用了一個for迴圈,遍歷了陣列中的n個元素一次。
空間複雜度(Space Complexity):O(1)。這題只使用了固定的額外空間來儲存兩個指標i和k,沒有創建與輸入大小相關的新陣列。這完全符合「就地(in-place)」的要求。