ゼロから始めるLeetCode Day21 「448. Find All Numbers Disappeared in an Array」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day20 「134. Gas Station」
次回
ゼロから始めるLeetCode Day22「141. Linked List Cycle」

問題

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をする、というものを最終的に返す、という処理で書きました。

シンプルな処理ゆえに書き方一つで計算量などが大きく変わるのは考えていて面白いですね。

良さげな回答があれば追記します。