因為陣列已經是排序好的,這是解決這個問題的關鍵。重複的元素會彼此相鄰。所以可以利用這一特性,使用雙指標(Two Pointers)的方法在O(n)時間複雜度和O(1)額外空間複雜度下解決問題。
首先,設置兩個指標:
慢指標(i或uniqueIndex):追蹤下一個唯一元素應該放置的位置。它同時也代表了目前找到的唯一元素的總數k。
快指標(j或runner):用來遍歷整個陣列,尋找新的唯一元素。
設置完後,初始化慢指標I = 0。而快指標j從1開始遍歷陣列到結尾。在每一步,比較nums[i]和nums[j]:如果nums[i]≠nums[j],這表示nums[j]是一個新的唯一元素。這時將慢指標i向前移動一步(i++),而這個新的唯一元素nums[j]賦值給新的唯一元素位置nums[i](即nums[i] = nums[j]);如果nums[i] = nums[j],這表示nums[j]是重複元素。這時不移動慢指標i,直接讓快指標j繼續向前移動,直到找到下一個不同的值。
迴圈結束後,慢指標i所在的位置就是唯一元素的最後一個索引。因此,唯一元素的總數k就是i + 1。