ゼロから始めるLeetCode Day64「287. Find the Duplicate Number」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day63 「195. Tenth Line」

次回
まだ

Twitterやってます。

問題

287. Find the Duplicate Number

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

問題としては、各整数が1からnまでの間にあるn + 1の整数を含む配列numsが与えられたとき，少なくとも1つの重複した数が存在しなければならないことを証明してください。
重複する数が1つしかないと仮定して，重複する数を求めるアルゴリズムを設計してください。

Example 1:
Input: [1,3,4,2,2]
Output: 2

Example 2:
Input: [3,1,3,4,2]
Output: 3

Note:
配列を変更してはいけません（配列は読み取り専用と仮定してください）。
定数，O(1) の余分な空間のみを使用しなければなりません。
実行時の複雑さは，O(n2)以下でなければなりません。
配列の中に重複する数は1つだけですが，それが複数回繰り返される可能性があります。

解法

読み取り専用であり、ソートできないという制約があるのを見落とさずに確認しておきましょう。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low,high = nums[0],nums[nums[0]]
        while low != high:
            low,high = nums[low],nums[nums[high]]
        low = 0
        while low != high:
            low,high = nums[low],nums[high]
        return low
# Runtime: 64 ms, faster than 86.19% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.4 MB, less than 35.59% of Python3 online submissions for Find the Duplicate Number.

lowとhighでそれぞれ要素をもち、numsの中の要素を代入し続けていくのをlowに0を代入して繰り返すことによってlowが答えになります。

少し解法としては物足りない部分があるかもしれませんが、今回はここまで。
お疲れ様でした。