leetcode

どーも!

たかぽんです!

今回は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)

それでわ!

おすすめの記事