Find the Duplicate Number
n+1 個の整数からなる配列 nums が与えられます。各整数は 1 から n までの範囲にあります。ちょうど 1 つの値が複数回（何度も出現する場合もあります）現れ、その値を返します。
nums を変更せず、追加メモリを定数量だけ使用して解いてください。
関数
- numsinteger-array
- それぞれ1からnまでのn+1個の整数
- 戻り値integer
- 複数回現れる値
制約
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- ちょうど1つの値が2回以上現れ、それ以外のすべての値は最大1回しか現れません。
例
- 入力
- nums = [2, 5, 1, 3, 5, 4]
- 出力
- 5
- 説明
- ここでは
nは5で、5は位置1と4にあるため、答えは5です。1から5までのその他の値は、それぞれ1回ずつ現れます。
- 入力
- nums = [4, 2, 4, 1, 4]
- 出力
- 4
- 説明
- 4は位置0、2、4に3回現れますが、3はまったく現れません。繰り返しは複数の欠けている値の代わりになるため、答えは4です。
提出時に隠しテスト+17件
発展問題
値に対する二分探索では、どちらのルールも O(n log n) 時間で保てます。O(n) 時間で保てますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての値は1から
nまでの範囲にあり、配列の位置は0からnまでです。したがって、すべての値は有効な位置でもあります。位置0から始め、位置nums[0]に移動し、次にその値が示す位置へ進む、といったことを繰り返します。この移動では何が起こるはずでしょうか？歩行は決して止まらず、訪れる位置は
n+1個しかないため、ループに入ります。ループに入る位置には2つの異なる位置から到達し、そのどちらもその位置を値として持っています。位置 0 から 2 つのポインターを使ってループの入口を見つけます。一方はラウンドごとに 1 回、もう一方は 2 回ジャンプさせ、同じ位置に到達するまで進めます。次に、一方を 0 に戻し、両方を 1 回ずつジャンプさせます。入口で合流し、そこが答えです。
解説
ハッシュセットやソートを使えば重複をすぐに見つけられますが、どちらもルールに反します。セットにはすべての値を保存するメモリが必要で、ソートするとnumsが変更されます。解決の鍵は数値にあります。すべての値は1からnの間なので、配列内の有効な位置でもあります。各値を別の位置へのリンクとして読み取り、位置0からリンクをたどると、必ずループに行き着き、その入り口が重複値です。Floydの速いポインターと遅いポインターを使えば、2つの整数でその入り口を見つけられます。
すべてのペアを比較する
正しいが、最大のテストでは終わらない
考え方
重複する値は、少なくとも2つの位置 i < j にあります。各位置を、それより後のすべての位置と比較します。値が等しい最初のペアが答えになります。最初の例では、位置1に5があり、位置2以降を調べると位置4にもう一つの5が見つかります。
これなら両方のルールを守れます。何も書き込まず、使うメモリは2つのループカウンターだけです。ペア同士を比較するため、処理は遅くなります。n+1 = 10,001個の値があり、両方の重複値が末尾近くにある場合、約5 × 10^7個のペアを調べます。
アルゴリズム
- 0 から末尾までの各位置
iについて: iより後の各位置jについて、nums[i]とnums[j]を比較します。- 最初に一致した時点で
nums[i]を返します。
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeat値に対する二分探索
考え方
位置ではなく、値の範囲を探索します。しきい値 m を選び、nums の要素のうち m 以下のものがいくつあるか数えます。
重複している値 d が m より大きい場合、値 1 から m はそれぞれ最大 1 回しか現れないため、個数は最大でも m です。d が m 以下の場合、m より大きい値はすべて最大 1 回しか現れないため、m より大きい要素は最大でも n-m 個で、m 以下の要素は少なくとも m+1 個あります。したがって、「count > m」という判定は d 未満のすべての m で偽となり、d 以上では真になります。二分探索で真に変わる最初の m を見つけると、それが d です。
2 つ目の例では、n は 4 です。m = 2 の場合、要素 2 と 1 によって個数は 2 となり、2 より大きくないため、答えは 2 より大きい値です。m = 3 の場合も個数は 2 のままなので、答えは 4 です。各反復では配列全体を 1 回読み取り、範囲を半分にするため、計算量は O(n log n) です。つまり、10,001 個の値を約 14 回走査します。
アルゴリズム
lowを 1 に設定し、highをnに設定します。これはnumsの長さから 1 を引いた値です。low < highの間、両者の中間にある値をmidとします。numsのうち、mid以下の要素の数を数えます。- その数が
midより大きければ、highをmidに設定します。そうでなければ、lowをmid+1に設定します。 lowを返します。
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return low値のリンクにおける Floyd の循環検出
考え方
配列をリンクとして読みます。位置 i は位置 nums[i] を指します。0 から n までの各位置には出リンクがちょうど1つあり、各リンクの行き先は1から n の範囲内です。最初の例では、リンクは 0 → 2、1 → 5、2 → 1、3 → 3、4 → 5、5 → 4 です。
位置0から始めて、リンクをたどります。各位置にはリンクがあり、位置は n+1 個しかないため、このたどり方は決して止まらず、いずれすでに通った位置に戻ります。それ以降は、ずっと同じ経路を回り続けます。この経路は、ギリシャ文字のρのように、尻尾の後にループが続く形です。最初の例では、たどる順序は 0, 2, 1, 5, 4, 5, 4, と続きます。尻尾は 0, 2, 1 で、ループは 5, 4 です。位置3は自分自身を指しますが、たどる経路はそこに到達しないため、問題ありません。
ループへの入口が重複値です。経路は異なる位置から2回5に入ります。1回目は尻尾の終端（位置1。nums[1] が5だから）から、2回目はループの終端（位置4。nums[4] が5だから）からです。異なる2つの位置に値5があるため、5が繰り返されます。値に0はなく、どのリンクも0に戻らないため、尻尾には必ず位置0が含まれます。したがって、入口には必ず異なる2つの入り方があります。繰り返される値はちょうど1つなので、入口がその値です。
次に、連結リストのサイクル検出と同様に、2つのポインターを使って入口を見つけます。フェーズ1では、同じループ内の位置で出会うまで、slow は1ラウンドに1つのリンクを、fast は2つのリンクをたどります。最初の例では、2つは4で出会います。フェーズ2では、slow を0に戻し、fast はその位置に置いたまま、両方を1ラウンドに1つのリンクだけ進めます。2つは入口で出会います。
フェーズ2が機能する理由を説明します。尻尾をたどって入口に着くまでに T 個のリンクがあり、ループの位置数を C とします。ポインターが出会ったとき、slow は s 歩、fast は 2s 歩進んでいます。2つは同じ位置にいたので、fast が余分に進んだ s 歩は、ループをちょうど整数回周回した分です。さらに T 歩進むと、slow は0から入口に到達します。一方、fast は、余分な周回は位置を変えないため、0から s+T 歩進んだ経路上の位置にいます。これは入口までの T 歩に s 歩を加えたもので、s 歩はループをちょうど整数回周回するため、fast も入口に着きます。これより早く出会うことはありません。なぜなら、slow はまだ尻尾にいて、fast はループから出ないからです。最初の例では、slow は 2, 1, 5 と進み、fast は 5, 4, 5 と進んで、T = 3 歩後に5で出会います。
各フェーズにかかるのは O(n) 歩で、メモリは2つの位置分だけであり、nums に書き込むことはありません。
アルゴリズム
- 各位置
iを位置nums[i]につながるノードとして扱い、両方のポインターを位置 0 から開始します。 - フェーズ 1:
slowをnums[slow]に、fastをnums[nums[fast]]に移動し、両者が等しくなるまで繰り返します。 - フェーズ 2:
slowを 0 に戻します。 - 両者が等しくなるまで、1 回に 1 つずつリンクを移動します。
slowはnums[slow]に、fastはnums[fast]に移動します。 - その位置を返します。そこが重複している値です。
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
落とし穴と境界ケース
誤答の多くは、位置と値を混同すること、または Floyd 法を1段階早く終えてしまうことが原因です。
- フェーズ1での合流地点を返す。これはループ上の位置であり、必ずしも入口とは限りません。最初の例ではポインターは4で合流しますが、答えは5です。
- 最初の移動の前に
slow == fastを確認する。どちらも0から始まるため、ループはすぐに終了します。先に移動してから比較するか、最初から1リンク先と2リンク先に配置します。 - 位置0以外から歩き始める。値に0がないため、位置0を指すリンクはなく、それによって末尾があることが保証されます。別の位置から始めると、最初の例の位置3のように、外側から入る方法のないループに入る可能性があり、そのループの入口は何の証明にもなりません。
- 重複する値はちょうど2回現れると思い込む。合計を使う方法、つまり合計から
1 + 2 + ... + nを引く方法では、2番目の例で15から10を引いて5になりますが、答えは4です。XOR を使う方法も同様です。 - 値ではなく位置を二分探索する、または
count >= midを判定する。1からmまでの値に重複も欠落もない場合、m以下の値の個数はちょうどmです。そのため、両側を分けるのは>だけです。 nums[x]を反転して訪問済みの値を示したり、値を所定の位置に入れ替えたりする。どちらの方法も機能しますが、どちらも配列を変更します。これはタスクで禁止されています。
よくある質問4
重複する数を見つけるアルゴリズムの時間計算量はどれくらいですか？
Floydの循環検出は、O(n)時間、O(1)の追加メモリで実行できます。2つのフェーズはそれぞれ、最大でもnの数倍のリンクをたどります。値に対する二分探索は、O(n log n)時間、O(1)のメモリを使用します。すべてのペアを比較する場合はO(n²)です。
Floydのサイクル検出で重複する数値が見つかるのはなぜですか？
各値を、その位置から値が示す位置へのリンクとして読むと、位置 0 からの移動は必ずループで終わります。移動は止まらず、進める場所は n+1 か所しかないためです。ループに入る位置には、尻尾上の位置とループ上の位置という異なる2つの位置から到達するため、2つの要素がその値を持ちます。Floydの方法は2つのポインターを使ってループの入口を見つけるため、重複した値を見つけます。
ハッシュセットを使ったり、配列をソートしたりしないのはなぜですか？
どちらも O(n) または O(n log n) の時間で答えを見つけられ、実際のプログラムではどちらを使っても問題ありません。この課題では、意図的にそれらを禁止しています。ハッシュセットは追加で O(n) のメモリを使い、ソートは nums を変更するか、完全なコピーを必要とするためです。この制約があるからこそ、サイクルとして捉える方法へと導かれます。
「重複する数を見つける」では、なぜ合計の公式が使えないのでしょうか？
配列の合計から 1 + 2 + ... + n を引くと、重複値がちょうど2回現れ、ほかのすべての値が1回ずつ現れる場合に限り、その重複値が得られます。ここでは、同じ値が何度も現れ、欠けている値の代わりになることがあります。[4, 2, 4, 1, 4] では、差は15引く10、つまり5ですが、配列に5はありません。
Python
def findDuplicate(nums):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [2, 5, 1, 3, 5, 4]
期待値
5