Find Minimum in Rotated Sorted Array
相異なる整数のリストを昇順に並べた後、回転させました。つまり、先頭からいくつかの要素（0個の場合もあります）を取り出し、同じ順序で末尾に移動しました。たとえば、[2, 5, 9, 11, 13, 15, 17]を3つ分回転させると、[11, 13, 15, 17, 2, 5, 9]になります。回転させたリストnumsが与えられます。O(log n)時間でその最小値を返してください。
関数
- numsinteger-array
- 回転された、重複のない整数のリスト
- 戻り値integer
- nums 内の最小値
制約
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104-
numsのすべての値は異なります。 numsは、あるkだけ回転された昇順のリストです（0 ≤ k < nums.length）。k = 0の場合、回転されていない状態です。
例
- 入力
- nums = [11, 13, 15, 17, 2, 5, 9]
- 出力
- 2
- 説明
- 値は11から17まで増加し、その後2まで下がります。そこで2回目の実行が始まります。探索ではインデックス3で17 > 9となるため、最小値はその右側にあります。その後、5 ≤ 9と2 ≤ 5によって
hiが戻され、範囲はインデックス4のみとなり、そこには2が含まれています。
- 入力
- nums = [4, 7, 10, 12]
- 出力
- 4
- 説明
- このリストは 0 だけ回転しているため、引き続きソートされており、最小値は先頭の値です。中央の値はどれも末尾の値以下なので、
hiは、4 が格納されているインデックス 0 に達するまで左へ移動し続けます。
- 入力
- nums = [30, -6, 0, 8, 19]
- 出力
- -6
- 説明
- 4つの値が先頭から末尾へ移動したため、最大値の30が先頭に来て、最小値の-6はインデックス1にあります。探索範囲がインデックス0と1に縮まり、30 > -6であることを確認して、
loを1に移動します。
提出時に隠しテスト+17件
発展問題
ソートせずに、nums の k 番目に小さい値を O(log n) 時間で返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ソート済みリストでは、各値はその前の値より大きくなっています。回転によって、それがちょうど1か所で崩れます。その場所に対して、最小の値はどこにありますか？
範囲の中央の値と最後の値を比較します。中央の値のほうが大きければ、その後のどこかで値は下がるはずです。中央の値のほうが小さければ、中央から最後までの区間では一度も下がることなく値が上がります。
loとhiで最小値を挟みます。nums[mid] > nums[hi]の場合はloをmid + 1に移動します。そうでなければ、mid自体が最小値である可能性があるため、hiをmidに移動します。loとhiが等しくなったら終了します。
解説
回転されたソート済みリストは、増加する2つの区間、[11, 13, 15, 17]と[2, 5, 9]で構成されています。最小値は2つ目の区間の最初の値で、値が下がる唯一の箇所のすぐ後にあります。リストを順にたどれば、O(n)でその下がり目を見つけられます。範囲の最後の値と中央の値を比較すると、中央の値が下がり目のどちら側にあるかがわかるため、二分探索ならO(log n)で見つけられます。
値が下がるまで歩く
考え方
ソート済みリストでは、それぞれの値はその前の値より大きくなっています。リストを回転させても、どちらの連続部分もソート済みのままで、順序が崩れる場所は1か所だけです。それは、最大値の次に最小値が続く場所です。そこで、左から右へ進み、左隣より小さい最初の値を返します。そのような値がなければ、リストは0回回転しており、最小値はnums[0]です。
[11, 13, 15, 17, 2, 5, 9]では、13、15、17はそれぞれ直前の値より大きいため、そのまま進み、2が17より小さいインデックス4で停止します。これはすべての値の最小値を求めるよりも効率的です。値が下がるところで停止するからです。しかし、その下がる場所はどこにあるかわかりません。[2, 3, 4, 5, 6, 7, 8, 1]のように、回転によって要素が1つだけ移動した場合、リスト全体を読み取ることになります。要素が5000個なら比較は5000回ですが、二分探索なら13回です。
アルゴリズム
- 1 から
n-1までの各インデックスiについて、nums[i]とnums[i-1]を比較します。 nums[i] < nums[i-1]の場合は、nums[i]を返します。2つ目の並びはそこから始まります。- ループが終了した場合、リストは回転されていません。
nums[0]を返します。
def findMin(nums):
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
return nums[i] # the only drop: the second run starts here
return nums[0] # no drop: the list was not rotated最後の値に対する二分探索
考え方
1つの約束を守ります。最小値はloとhiの間（両端を含む）にあります。最初、この範囲はリスト全体です。中央の値を見て、範囲の最後の値であるnums[hi]と比較します。
nums[mid] > nums[hi]なら、midとhiの間のどこかで値が下がっており、最小値はその下がった直後の値、つまりmidより右にあります。そこでlo = mid + 1とします。それ以外の場合はnums[mid] < nums[hi]（値はすべて異なります）なので、nums[mid..hi]は途中で下がることなく増加しています。したがって、最小値はnums[mid]か、それより前にあります。そこでhi = midとします。midを飛び越えてはいけません。そこが最小値かもしれないからです。どちらの移動でも約束は保たれ、範囲は狭まります。そしてloとhiが一致すると、残った1つの値が最小値です。
最初の例[11, 13, 15, 17, 2, 5, 9]をたどってみましょう。範囲0から6の中央は3で、その値は17です。これはnums[6] = 9より大きいので、loは4になります。範囲4から6の中央は5で、その値は5です。9より大きくないので、hiは5になります。範囲4から5の中央は4で、その値は2です。5より大きくないので、hiは4になります。nums[4] = 2を返します。
各ステップで範囲は半分になるため、ループの実行回数は最大でおよそlog2(n)回です。要素数が5000の場合は13ステップで、追加メモリはインデックス2つ分です。
アルゴリズム
lo = 0とhi = n-1を設定します。lo < hiの間、mid = lo + (hi - lo) / 2を計算します。nums[mid] > nums[hi]の場合、lo = mid + 1を設定します。- それ以外の場合は、
hi = midを設定します。 - ループが終了したら、
nums[lo]を返します。
def findMin(nums):
lo, hi = 0, len(nums) - 1 # the minimum sits in nums[lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the values drop after mid, so the minimum is right of it
else:
hi = mid # nums[mid..hi] climbs: the minimum is at mid or left of it
return nums[lo]
落とし穴と境界ケース
このループは4行で、それぞれの行には、つい書いてしまいそうな誤った書き方があります。
- 2つ目の分岐で
hi = mid - 1と書くこと。この分岐は、midが最小値そのものかもしれない場合に実行されます。[3, 1, 2]では、中央の値1は2より大きくないため、hiは0になり、関数は3を返します。 lo ≤ hiを条件にループすること。loとhiが等しくなると、midも両方と等しくなり、nums[mid] > nums[hi]は偽になります。そしてhi = midとしても何も変わらず、ループは終わりません。範囲に要素が1つ残ったら停止するように、lo < hiを使います。nums[hi]ではなくnums[lo]と比較すること。回転していないリスト[1, 2, 3, 4, 5]では、中央の値3はnums[0] = 1より大きいため、最小値は右側にあるように見えます。そのため、探索はインデックス0にある本当の最小値から遠ざかり、4を返します。nums[lo]ではなくloを返すこと。課題が求めているのは値です。インデックスは別の問いに対する答えです（回転回数についてはFAQを参照してください）。- リストは回転済みだと仮定すること。回転数が0の場合もあり、フォールバックなしで落ち込みを探すコードは、範囲外を読み取るか、何も返しません。落ち込みが存在しない場合は
nums[0]を返します。
よくある質問4
回転したソート済み配列で最小値を見つける時間計算量は何ですか？
二分探索を使えば、時間計算量はO(log n)、追加の空間計算量はO(1)です。各ステップで範囲の半分を残すため、要素数が5000のリストでも比較は最大13回です。最小値が末尾にある場合、下降位置を探す走査ではすべての要素を読み取るため、時間計算量はO(n)です。
なぜ nums[mid] を nums[lo] ではなく nums[hi] と比較するのでしょうか？
nums[hi]は最小値がどちら側にあるかを常に確定できる一方、nums[lo]では確定できないためです。nums[mid] > nums[hi]なら、値はmidとhiの間にあるはずです。そうでなければ、nums[mid..hi]は単調増加しており、最小値はmidまたはその手前にあります。nums[lo]の場合、nums[mid] > nums[lo]という結果は、最小値がnums[lo]である未回転のリストにも、midより右に最小値がある回転済みのリストにも当てはまります。
ソート済み配列が何回回転されたかは、どのように求めますか？
同じ二分探索を実行し、nums[lo]の代わりに最小値のインデックスであるloを返します。回転を最後の要素を先頭に移動することと数えるなら、そのインデックスが回転数です。この問題のように、最初の要素を末尾に移動することと数えるなら、回転数は(n - lo) mod nです。[11, 13, 15, 17, 2, 5, 9]では最小値のインデックスは4で、7から4を引くと、移動した値の数である3になります。
配列に重複する値がある場合でも、二分探索は機能しますか？
変わらないわけではありません。[2, 2, 2, 0, 2]では、nums[mid]がnums[hi]と等しくなることがあり、その場合はどちらの側も除外できません。その場合にhi = hi - 1で範囲を狭めても安全です。nums[hi]と同じ値がmidの位置に範囲内で残るためです。ただし、同じ値が並ぶ中に小さい値が1つ隠れているリストでは、O(n)のコストがかかります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def findMin(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [11, 13, 15, 17, 2, 5, 9]
期待値
2