何を書いている記事なのか
LeetCodeというサイトでプログラミングの問題を解きながら、効率の良いコードを書けるようになるよう修行しています。
その過程をブログに残しておこうと思い、書きました。
私の最初の回答、リファクタリング後の回答、その他気づきや学びを記したいと思います。
今回の問題は、
「26. Remove Duplicates from Sorted Array」です
leetcode.com
問題の詳細
難易度はEasyです。
私にはまだ、Easyしか解ける力がありません。日々精進あるのみ。
問題文はこちら。
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
要するに、「ソートされた配列が入力として与えられるので、配列内のダブりを無くし、加工後の配列のlengthを返せ」ということですね。
私の最初の回答
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
del_idx = []
new_nums = []
for i, num in enumerate(nums):
del_idx.append(i) if num in new_nums else new_nums.append(num)
for i, idx in enumerate(del_idx):
del nums[idx - i]
return len(nums)
これは、正解こそしたものの、実行時間は下から数えて全体の6.03%、メモリー使用量は下から数えて全体の5.43%という惨憺たる結果でしたwwww
まあ、ここで課題が見つかったことをポジティブに捉えつつ、頑張ってリファクタリングしていきます。
上記のコードのまずそうなところを予想すると、
- まず、新しく空の配列を二つも用意して処理していて、メモリ効率悪い。
- ループが2回あって、処理速度が遅い
新しい配列を使わない、かつループの回数を抑えるには、1度のループでダブりチェックと排除の両方の仕事をこなさないとなりません。
他の人がどうしてんのかチラ見してみると、whileを使ったり、integerを一緒に走らせたりと色々工夫を凝らしています。
それらをパクって参考にしつつ、修正したコードがこちら。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
else:
i,j=1,1
while j<len(nums):
if nums[i-1]!=nums[j]:
nums[i]=nums[j]
i+=1
j+=1
return i
いやあ、賢いやり方ですねえ。
自分の力だけでこれだけ書けるようになりたいものです。先は長い。
ただ、これでもスピードは全体の50%くらいの立ち位置でした。
メモリ効率に至っては、最初の私のコードとほとんど立ち位置が変わってないという状況。
LeetCodeの世界は厳しい。
気づき・学び
LeetCodeの世界では、新しい変数を作ることによるメモリの発行。ループ処理による速度の問題に対して、かなり気を使わねばならないということを改めて痛感した問題でした。
1つの変数、1つのループにどれだけ意味を持たせられるかが勝負です。分かっていてもできないのですけどもね。。。
今回賢いなあと思ったのは、"i"という遅い進み方をする変数と、"j"という速い進み方をする変数を使って、配列のダブりを徐々に消していくという処理。ソートされた配列という前提があるからこそ使える技ですが。
私の引き出しの一つにしたいと思います。
今回はこれで以上です。
