NeetCode 150 [Linked List]medium:Find the Duplicate Number

NeetCodeのSolutionを書いていく

Find the Duplicate Number

問題

n + 1 個の整数を含む配列numsが与えられます。
それぞれの整数は1~nの間の値です。

一つの数字だけを除き、すべての整数は一度だけ登場します。
2度以上登場する数字を返しなさい。

制約

• 1 <= n <= 10000
• nums.length == n + 1
• 1 <= nums[i] <= n

計算量：O(n)
メモリO(1)

例

Input: nums = [1,2,3,2,2]
Output: 2

Input: nums = [1,2,3,4,4]
Output: 4

メモ

メモリがO(1)なのがポイント。
メモリの制限がなければSetに格納しながら2度登場する数字を探せば良い。

ヒントを見ると、与えられた配列に以前登場した数字かどうかを保持させて使えばよいとのこと。
更にその方法として下の数字に-1をかけることで実現できるとのこと。
入力が正と限られているからできることですね。

またもう一つの工夫として、i番目の配列の値そのものを負にしてもだめ。
これだとInで検索するときにO(n)の時間がn回かかるのでO(n^2)になってしまう。
「i番目の値番目」の配列の値をマイナスにする必要がある。
こうすると、配列の値が以前登場したかどうかは配列の参照O(1)で済むのでn回でO(n)になる。

from typing import List


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for num in nums:
            num = abs(num)
            if nums[num - 1] < 0:
                return num
            nums[num - 1] *= -1
        return -1