問題の説明
指定された値（val）をリストから削除し、残った要素の数を算出するアルゴリズムです。
解法
アプローチ 1.
1) valがnumsにある限りnumsを走査して削除します。 2) 削除と同時に末尾に _ を追加します。 3) 発見するたびにcntを増やし、これを元の長さから引いて返します。
1
2
3
4
5
6
7
8
9
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
org_len = len(nums)
cnt = 0
while val in nums:
nums.remove(val)
nums.append("_")
cnt += 1
return org_len - cnt
上記解法の時間複雑度と空間複雑度は次の通りです。
- 時間複雑度: O(N^2)
- remove関数の時間複雑度がO(N)であり、これをnumsの要素数だけ繰り返すためO(N^2)の時間複雑度がかかります。
- 空間複雑度: O(1)
- 単純ないくつかの変数しか使用していないため、O(1)です。
この方法は時間複雑度がO(N^2)であるため、入力が多くなると実行時間が長くなり、タイムアウトの可能性が高いです。
アプローチ 2. Two Pointer
Two Pointerを使用して、左右の2つのインデックスを調整しながら重複した値を削除しました。 1) leftとrightという2つのインデックスを0から始め、 2-1) rightがvalの場合、_に変換し、rightは1つ右に移動します。 2-2) rightがvalでない場合、leftとrightを交換し、両方とも1つずつ同時に移動します。
このロジックに従うと、3223という入力で3を削除する場合、以下のフローになります。
1
2
3
4
5
3223
_223 <- rightが3なので_に変更し、rightは1つ右に移動
2_23 <- leftとrightが異なるので
22_3 <- 2つの値を交換
22__ <- rightが3なので_に変更
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left, right = 0, 0
while right < len(nums):
if nums[right] == val:
nums[right] = '_'
right += 1
else:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
return left
- 時間複雑度: O(N)
- numsのサイズだけ時間がかかります。
- 空間複雑度: O(1)
- 単純ないくつかの変数しか使用していないため、O(1)です。