Problem
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
この問題は、指定された値と等しくない要素のみを持つように配列を変更し、そのような要素の数を返すことを求めています。
InputとOutputの例は次になります。
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Outputのnums配列については、最初の5つの要素が正しければ何でもよく、順番も関係ありません。そのため、[0,0,1,3,4]としたり[0,1,4,0,3,X,X,X]としてもpassします。
Trickyな点としては、配列操作をin-placeに実行するという制約です。つまり、既存の配列のみを使い、追加の配列を作成してはいけないということです。
https://leetcode.com/problems/remove-element/description/
Key Idea
配列を2つのポインタを使います。
１つ目のポインタは、fast-runnerとして、配列を走査するために利用します。
In placeにnumsというリストを変更するため、
Outputとして、numsというリストをin-placeに操作して、左からk個の要素全てがvalではないように並び替える必要があります。
ここで「どこまで並び替えたか」を管理するのに2つ目のポインタを使います。(slow-runner)
言い換えると、このポインタより左の要素は、全てvalではない値で統一されているという仕切りになります。
簡単に手順を書くと下記のようになります。ここではfast-runnerをreader, slow-runnderをwriterという名称にしています。
Approach 1
上記のアイデアは、下記の様にかけます。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
k = 0
writer = 0
for reader in range(len(nums)):
if nums[reader] != val:
nums[writer] = nums[reader]
k += 1
writer += 1
return k
ここで、kとwriterは実質同じ挙動になっていることがわかります。そのため、writerというポインタをなくして、kを活用することができます。
Approach 1'
kとwriterという２つの変数が冗長であるため、一つにまとめることができます。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
k = 0
for reader in range(len(nums)):
if nums[reader] != val:
nums[k] = nums[reader]
k += 1
return k
計算量は下記の様になります。
- Time Complexity： O(n)
ここで、nは配列numsの要素数です。これは、アルゴリズムが配列の各要素を一度だけ走査するためです。
- Space Complexity： O(1)
入力のサイズに関わらず、使用するメモリ量は一定です。