問題の説明
LeetCode 26. Remove Duplicates from Sorted Array
ソートされた配列から重複を削除し、残った要素の値を返すアルゴリズムです。
解法
アプローチ: Two Pointer
Two Pointerを使用して、左右の2つのインデックスを調整しながら重複した値を削除しました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
アプローチ: Two Pointer
#0011122334
ij <- iとjが同じ場合
i j <- jだけ1つ上がる
#0011122334 <- iとjが異なる場合
ij <- iを1つ上げて
#0101122334 <- 2つの値を交換
i j <- jを1つ上げる
#0101122334 <- 2つの値を交換
i j <- iとjが同じ場合はjを1つ上げる
i j <- iとjが異なる場合は
i j <- iを1つ上げる
#0121102334 <- 2つの値を交換
... <- これを繰り返す
このようにiとjを移動させながら処理すると、重複した値が削除されます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
j = 1
cnt = 1
while i < len(nums) and j < len(nums):
if nums[i] == nums[j]:
j += 1
else:
i += 1
nums[i], nums[j] = nums[j], nums[i]
j += 1
cnt += 1
return cnt
上記解法の時間複雑度と空間複雑度は次の通りです。
- 時間複雑度: O(N)
- numsのサイズだけ時間がかかります。
- 空間複雑度: O(1)
- 単純ないくつかの変数しか使用していないため、O(1)です。