どーも！
たかぽんです！
今回はRemoveDuplicates from Sorted Arrayを解いていきます！
Remove Duplicates from Sorted Array
問題は以下です。
こちらの問題を簡単に説明しておくと、配列の中に重複した値がたくさんあります。
その重複した値を全て排除し、その長さを返す...というものです。
ただし、参照私で配列が渡されるため、その参照元も同じく重複をのぞいた形にしなければいけません。
（筆者は一度別の配列に作る形にしてwrong answerいただきました...w)
上記リンク先の例ですが...
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]上記のように、0や1で被っている場合、参照で渡されてきたnumsから重複する要素をすべて除外していきます。
そして、最終的に全て除外した配列の長さ(5)を返す...といった形です。
Outputが正しくても、参照下の配列が書き換えられていない場合、それはwrong answerとなります。
では、次に簡単なアルゴリズムをみていきましょう！
アルゴリズム
さて、やることは至って簡単です。
初めて値が出現した際、それを別の配列に持たせ、次の要素以降、その配列に値が入っているかどうかを確認するようにして、入っていれば追加しない...といった具合にすれば良さそうです。
ただし、一番気をつけないといけないのが、今回はnumsをちゃんと書き換えないといけません。
そのため、筆者の場合、一度numsの中身をすべてtmpとして、別の配列にそのまま書き出しました。
numsの中身をpopで出し、代わりにtempとして0番目の要素を後ろにくっつけていく感じです。
（この際、配列の要素を取り出していくforだと、numsからpopして要素を引くと、回る回数が少なくなったため、配列長分でforを回す必要がありました...!）
そして、書き出したtempからnumsの配列へ戻す際に、numsにまだその値が存在しなければ追加、存在している場合は追加しない...といった形にしているだけです。
最後にはnumsの配列長を返します。
numsの参照元は参照先でいじればそれで変わってくれるため、特に返したりはしなくてOKです。
正直一回コピーしてしまっているので計算量は多い気がしますが、いったんは動いたのでよし...
いつか二週目等では速度考慮して色々考えたいですね...
最後に提出したコードを貼っておきます。
提出したコード
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
temp = []
for i in range(len(nums)):
temp.append(nums[0])
nums.pop(0)
for i, num in enumerate(temp):
if num not in nums:
nums.append(num)
return len(nums)それでわ！