## 題目
Given an integer array `nums` sorted in **non-decreasing order**, remove some duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears **at most twice**. The **relative order** of the elements should be kept the **same**.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.
Return `k`_ after placing the final result in the first _`k`_ slots of _`nums`.
Do **not** allocate extra space for another array. You must do this by **modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm)** with O(1) extra memory.
**Custom Judge:**
The judge will test your solution with the following code:
```
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
```
If all assertions pass, then your solution will be **accepted**.
**Example 1:**
```
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
**Example 2:**
```
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
**Constraints:**
- `1 <= nums.length <= 3 * 104`
- `-104 <= nums[i] <= 104`
- `nums` is sorted in **non-decreasing** order.
## 題解紀錄
依照題意要求可以得知：
1. nums是升序排列的
2. 因為依據題目要求，刪除重複項到最後需要有兩個留下來，所以只有3個以上的重複項才需要**刪除**
題解 1：
```python=
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# 依據 2. 可以得知陣列中如果出現**三個**一樣的數字時，才需要刪除，所以使用3個指針分別指向陣列中的 0,1,2 位置
i = 0
j = 1
t = 2
result = len(nums)
if len(nums) < 3: # 邊際條件：因為只有三個數字以上重複的時候才會需要刪除，所以三個數字以下的陣列可以直接返回
return len(nums)
while i < len(nums) and j < len(nums) and t < len(nums):
compare = nums[i] == nums[j] # 比對 i 和 j 是否一致
if compare:
target = nums[j]
while t < len(nums): # 確保 t 不超出邊界
if nums[t] == target: # 如果數字和前面重複的數字一致，則刪除
nums.pop(t)
result -= 1
else:
break
# 全部指針往前移，繼續比對
i += 1
j += 1
t += 1
return result
```
題解 2：
雙指針解法
此解法是依據 **題解1** 優化而來，主要優化思路為：
因為陣列為升序排序，所以當兩個指針中間空一格時 [(1),1,(1)]，數字還一樣的時，說明中間那個數字也必定和前後兩數字相同，故判定前面指針的數字為重複項，可以刪除。
```python=
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) < 3: # 邊界條件一樣
return len(nums)
i = 0
j = 2
while i < len(nums) and j < len(nums):
while j < len(nums):
if nums[i] == nums[j]:
nums.pop(j)
else:
break
i += 1
j += 1
return len(nums)
```
相比於 **題解 1** 的 **68ms** 優化到了 **57ms**
題解 3:
根據其他人的題解啟發思考修改而來
這題是雙指針的解法，但是其實是藉由題目的特性巧妙的定位了三個位置來解題
```python=
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""
[1,1,1,1,1,2,2,2,3]
x i
j
[1,1,1,1,1,2,2,2,3]
x i j
[1,1,1,1,1,2,2,2,3]
x i j
[1,1,1,1,1,2,2,2,3]
x i j
[1,1,2,1,1,2,2,2,3]
x i j
[1,1,2,2,1,2,2,2,3]
x i j
[1,1,2,2,1,2,2,2,3]
x i j
[1,1,2,2,3,2,2,2,3]
x i j
"""
total_length = len(nums)
if total_length < 3:
return total_length
i = j = 2
while i < total_length and j < total_length:
if nums[i-2] != nums[j]:
nums[i] = nums[j]
i += 1
j += 1
return i
```
以上的題解 時間複雜度為 O(n) 空間複雜度為 O(1)
Sign in with Wallet
Connect another wallet