ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
Twitterやってます。
前回
ゼロから始めるLeetCode Day47 「14. Longest Common Prefix」
次回
ゼロから始めるLeetCode Day49 「1323. Maximum 69 Number」
Twitterやってます。
問題
26. Remove Duplicates from Sorted Array
難易度はEasy。
問題としては、ソートされた配列が与えられます。
その配列から重複した要素を削除し、書く要素を1回だけ表示し、新しい長さを返す、という問題です。
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn’t matter what you leave beyond the returned length.
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn’t matter what values are set beyond the returned length.
#解法
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = 0
for i in range(1,len(nums)):
if nums[n] < nums[i]:
n += 1
nums[n] = nums[i]
return n+1
# Runtime: 84 ms, faster than 77.52% of Python3 online submissions for Remove Duplicates from Sorted Array.
# Memory Usage: 15.6 MB, less than 35.88% of Python3 online submissions for Remove Duplicates from Sorted Array.
最初から要素を舐めていき、それぞれのnumsのインデックスと用意したn
を比較し、 処理をしていく、という手法で書きました。
特に捻って書く必要もないですし、オーソドックスな処理と言えるのではないでしょうか。
この問題は配列とfor文とif文の使い方を学ぶには良い問題だと思うので、興味を持った初心者でも解けそうな感じなのでお勧めしやすいのではないでしょうか。
今回はここまで。お疲れ様でした。
コメント
コメントを投稿