📘 題目敘述
給定一個已排序（non-decreasing）的整數陣列 nums，請原地（in-place）移除重複的元素，使每個元素只出現一次。
回傳移除重複後的元素數量 k，並保證：
nums的前k個元素為不重複的結果- 超過
k之後的內容不重要
條件限制
1 ≤ nums.length ≤ 3 * 10^4-100 ≤ nums[i] ≤ 100nums已經排序完成
🧠 解題思路
這題的關鍵前提是：陣列已經排序。
因為已排序：
- 相同的數字一定會「連續出現」
- 只要和「前一個保留下來的值」比較，就能知道是不是重複
我的想法是用一個指標 pos，專門指向「下一個可以放入不重複元素的位置」。
整體概念是：
一邊掃描陣列，一邊把「第一次出現的數字」往前覆蓋，重複的就直接跳過
所有變數
nums：題目給定、同時也是要被原地修改的陣列n：nums的長度before：目前已經保留下來的「上一個不重複元素」pos：下一個不重複元素應該放入的位置（也是最後回傳的長度）
🪜 主要流程步驟
初始化階段
- 因為陣列至少有一個元素，第一個元素一定可以保留
- 設定
before = nums[0] - 設定
pos = 1，表示目前已經保留了 1 個不重複元素
逐一掃描陣列
接著我用一個 for 迴圈，從頭到尾掃描 nums。
對每一個 nums[i]，會出現兩種情況：
情況一：nums[i] == before
- 代表這個數字和上一個保留的數字一樣
- 屬於重複元素
- 直接跳過，不做任何事
情況二：nums[i] != before
- 代表這是一個新的、不重複的數字
- 把它放到
nums[pos] pos++，準備下一個位置- 同時更新
before = nums[i]
這樣做的效果是：
- 陣列前半段會逐步被「覆蓋成不重複版本」
- 後面的資料即使被覆蓋也沒關係，題目不在乎
回傳結果
當整個陣列掃描完：
pos就是「不重複元素的總數」nums[0] ~ nums[pos-1]就是答案內容
直接回傳 pos 即可。
💡 整體邏輯總結
- 利用「已排序」這個條件
- 只需要和前一個保留值比較
- 用一個指標
pos原地覆蓋陣列
時間複雜度是 O(n)，空間複雜度是 O(1)（只用常數額外變數）。
💻 程式碼實作
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int pos = 1;
int before = nums[0];
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] != before) {
nums[pos] = nums[i];
pos++;
before = nums[i];
}
}
return pos;
}
};
🔗 題目連結
https://leetcode.com/problems/remove-duplicates-from-sorted-array/