#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day20 「134. Gas Station」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
448. Find All Numbers Disappeared in an Array
難易度はeasy。Top 100 Liked Questionsの一つです。
Top 100 Liked Questionsのeasyの問題もだいぶ少なくなってきました。
1≦a[i]≦n（nは配列のサイズ）である整数の配列が与えられた場合、一部の要素は2回出現し、他の要素は1回出現します。
この与えられた配列において表示されない全ての要素を見つけます。
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
1~8の間で存在しない値が5と6なのでその二つが返されています。
解法
今回最初に実装したのは、配列をソートし、そのソートした配列と元の配列を比較した上で存在しない値を返す配列に追加していくというものです。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
num,ans = set(sorted(nums)),[]
for i in range(1,len(nums)+1):
if i not in num:
ans.append(i)
return ans
# Runtime: 464 ms, faster than 11.82% of Python3 online submissions for Find All Numbers Disappeared in an Array.
# Memory Usage: 23.7 MB, less than 7.14% of Python3 online submissions for Find All Numbers Disappeared in an Array.
ただし、あまり速いものではなく、メモリの消費量もそこまで節約できていません。
なので今回は他にも実装してみました。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for num in nums:
ans = abs(num) - 1
if nums[ans] > 0:
nums[ans] *= -1
return [i+1 for i in range(len(nums)) if nums[i] > 0]
# Runtime: 380 ms, faster than 63.11% of Python3 online submissions for Find All Numbers Disappeared in an Array.
# Memory Usage: 21.5 MB, less than 17.86% of Python3 online submissions for Find All Numbers Disappeared in an Array.
少し改善されました。
後者は絶対値を取得するabsを取得し、仮にnums[ans]がゼロより大きければnums[ans]に-1を欠けた値をnums[ans]を代入します。
最後に内包表記でnumsの長さを取得し、nums[i]>0であればi+1をする、というものを最終的に返す、という処理で書きました。
シンプルな処理ゆえに書き方一つで計算量などが大きく変わるのは考えていて面白いですね。
良さげな回答があれば追記します。