問題の説明
LeetCode 80. Remove Duplicates from Sorted Array II
配列から重複を最大2つだけ残して削除する問題
解法
アプローチ: Two Pointer
Two Pointer를 사용하여 두 개의 인덱스를 조정하면서 풀었습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
アプローチ: Two Pointer
#111223
ij <- 같으면 dup 1
ij <- 같으면 dup 1を増やす
ij <- dupが2以上ならjだけを上げる
i j <- 違うものが見つかると
ij <- iを上げる
#112123 <- 交換
i j <- 同じで、dupが2未満
ij
#112213
ij
i j <- 違うものが見つかる
ij <- iを上げて
#112231 <- 交換
ij <- 違うものが見つかる
i/j <- iを上げて交換
j <- j終了
위のロジックのようにiとjを動かしていくと、最大2つの重複が残り、それ以外は削除されます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# numsが空の場合は0を返す
if not nums:
return 0
i = 0
j = 1
dup = 1
while i < len(nums) and j < len(nums):
# アイテムが同じ場合
if nums[i] == nums[j]:
# 連続したアイテムがない場合、左のインデックスを上げて右のインデックスと交換
if dup < 2:
i = i + 1
nums[i], nums[j] = nums[j], nums[i]
# 連続したアイテムがある場合、右のインデックスを上げて、dupの値を上げる
j = j + 1
dup += 1
else:
i = i + 1
nums[i], nums[j] = nums[j], nums[i]
j = j + 1
dup = 1
return i + 1
上記解法の時間複雑度と空間複雑度は次の通りです。
- 時間複雑度: O(N)
- numsだけのループがあるため、O(N)の時間複雑度がかかります。
- 空間複雑度: O(1)
- 追加の空間は使用されません。