leetcode easy remove duplicate from sorted array

こんにちは

今回の学びは

・きちんと問題ぶんをよんで入力と出力をおさえましょう。

・どんな状態を記憶してく必要があるのか？で変数を決める

問題はすでにならべられている数字なのですが、重複があるのでそれを省いて、in-placeで書き換えてください

というもんだい

例えば

1, 1, 2だったら1, 2, xをかえしましょう　最後がxなのはなんでもいいからです

ふたつポインターつかって

ひとつは操作パス

もうひとつは書き込みパス　としましょう

実装前後でこれは毎回書きましょう。timespace anaylysis (時間とスペースの分析）は　操作パス一発なのでO(n)です

メモリはi, jの変数くらいなのでO(1)です

pseudocode（擬似コード）をかいてみますか。

j = 0 # write pointer
pre = S[0]
for i, x in S:
  if x == pre: # duplicate
     pass
  else:
     S[j] = x
     j+=1

シンプルですね。たぶん動くでしょう。

で、最初に提出したコードはこちら、ですがサンプルケースで通りません。なにが問題かわかりますでしょうか。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1 # write pointer
        if nums == None or len(nums) == 0: return 0
        pre = nums[0]
        dup = 0
        dup_pre = None
        for i, x in enumerate(nums):
            if i == 0:
                pass
            elif x == pre: # duplicate
                if x != dup_pre:
                    dup += 1
                dup_pre = x
            else:
                nums[j] = x
                j+=1
            pre = x
        return dup

間違いは、重複の数をかえすのではなく、重複を取り除いたあとの配列の長さをかえすべきだったのです。

問題文の入力と出力の理解が間違っていると、

要件定義をちゃんと理解していない、できない、と判断されてもおかしくないので、きちんと問題ぶんをよんで入力と出力をおさえましょう。

実際の実装はこちら

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1 # write pointer
        if nums == None or len(nums) == 0: return 0
        pre = nums[0]
        dup = 0
        dup_pre = None
        for i, x in enumerate(nums):
            if i == 0:
                pass
            elif x == pre: # duplicate
                if x != dup_pre:
                    dup += 1
                dup_pre = x
            else:
                nums[j] = x
                j+=1
            pre = x
        return j

なんとか一発パスです

実装後です。timespace anaylysis (時間とスペースの分析）は　◯◯　O(n) and space is O(1)

今回は何回か見たことがある問題ににていたので

パッとふたつのポインターをつかうということが

おもいつきました。

操作パスとは別に書き込み状態を持つ、ということが

発想の原点になるべきですね。

どんな状態を記憶してく必要があるのか？という質問をすることで 必要な変数がみえてきます。あたりまえのことを言っているようですが、これを意識するとぐっとコーディング力が上がります

以上です