Median of Two Sorted Arrays
整数のリスト nums1 と nums2 が与えられます。それぞれ小さい値から大きい値の順に並んでおり、少なくとも1つの値を含みます。両方のリストの値を合わせた中央値を、テキストとして返してください。
要素数の合計が奇数の場合、中央値は中央の値です。たとえば "4" です。偶数の場合は、中央にある2つの値の平均です。たとえば "2.5" や "-0.5" です。整数は小数点なしで表し、ゼロは "0" とし、"-0" とはしません。実行時間は O(log(min(m, n))) を目指してください。
関数
- nums1integer-array
- 最初のリスト。小さいものから大きいものへ並べ替え済み
- nums2integer-array
- 2つ目のリスト。小さい順に並んでいます
- 戻り値string
- すべての値の中央値。たとえば「4」や「-2.5」のようなテキスト
制約
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- 両方のリストは非減少順に並んでおり、値は重複する場合があります。
例
- 入力
- nums1 = [1, 4]nums2 = [2, 7, 9]
- 出力
- "4"
- 説明
- 値を合わせると、1、2、4、7、9です。5つの値には中央の値が1つあり、3番目の値である4です。
- 入力
- nums1 = [1, 2]nums2 = [3, 4]
- 出力
- "2.5"
- 説明
- 合わせると、値は1、2、3、4です。真ん中の2つの値は2と3で、その合計は5、5の半分は2.5です。
- 入力
- nums1 = [-7, -3]nums2 = [-2, 0]
- 出力
- "-2.5"
- 説明
- 値を合わせると -7、-3、-2、0 です。中央の値である -3 と -2 の合計は -5 で、その半分は -2.5 です。
発展問題
同じ切り分けを使って、任意のkについて、2つのリストの中からk番目に小さい値を対数時間で見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
2つのリストをマージすると、中央値を見つけるのに
O(m + n)かかります。これより効率を上げるには、中央値を分割点として考えてみましょう。つまり、すべてのm + n個の値を、同じサイズの下半分と上半分に分ける境界線です。下半分は、
nums1の接頭部分とnums2の接頭部分です。nums1からi個の値を取ると、nums2から取る個数も決まります。それぞれのリストから取った最後の値が、もう一方のリストに残った最初の値以下であれば、分割位置は正しいです。短い方のリストで
iを二分探索します。nums1から取った最後の値が大きすぎる場合は、そこから取る数を減らします。nums2から取った最後の値が大きすぎる場合は、取る数を増やします。適切な位置で分割すると、中央値は分割位置より下の最大値と上の最小値から求められます。この2つの整数を足して、自分で合計を2で割ります。
解説
リストをマージすると中央値を O(m + n) で求められますが、読み取る値のほとんどは答えに影響しません。中央値は下半分と上半分の境界がどこにあるかだけで決まり、その境界は1つの数で定まります。つまり、短い方のリストから下半分に含める値の数です。二分探索なら、O(log(min(m, n)) ) のステップでその数を見つけられます。
2つのリストを結合する
考え方
マージソートのようにリストをマージして、1つのソート済みリスト merged にします。total = m + n として、整数除算を使い、merged[(total-1)/2] と merged[total/2] を足します。合計が奇数ならどちらも中央の値で、偶数なら中央の2つの値なので、どちらの場合も合計の半分が中央値になります。
中央で処理を止めたとしても、マージでは値の半分を処理するため、時間計算量は O(m + n) です。
アルゴリズム
- リストを
mergedにマージし、常に現在の値が小さい方を取り、その後、残っているリストの残りを追加します。 total = m + nとして、merged[(total-1)/2]とmerged[total/2]を足します。- 合計の半分をテキストとして返します。合計が偶数なら2で割り、奇数なら符号、絶対値の半分、
.5の順に記述します。
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])カット位置での二分探索
考え方
下半分にはhalf = (m+n+1)/2個の値を含めます。合計が奇数の場合は、余分な1個も下半分に含めます。nums1の先頭からi個、nums2の先頭からj = half-i個を取ります。下半分のどの値も上半分のどの値より大きくなければ、分割位置は正しい状態です。各リストはソート済みなので、確認する条件はleft1 ≤ right2とleft2 ≤ right1の2つです。ここでleftはリストが下半分に渡す最後の値、rightはリストに残す最初の値です。片側に値がない場合は、マイナスまたはプラスの無限大として扱います。
left1 > right2ならiが大きすぎ、left2 > right1なら小さすぎます。したがって、iは0からmまでの二分探索で求められます。[1, 2]と[3, 4]では、i = 1はleft2 = 3 > right1 = 2で条件を満たさず、i = 2なら満たします。(2 + 3) / 2 = 2.5。
アルゴリズム
nums1が短い方のリストになるようにします。half = (m+n+1)/2とします。j = half-iとして、lo = 0からhi = mまでiを二分探索します。- 末端を越えた位置には無限大を設定し、
left1 = nums1[i-1]、right1 = nums1[i]、left2 = nums2[j-1]、right2 = nums2[j]を読み取ります。 left1 > right2なら、hi = i-1に設定します。left2 > right1なら、lo = i+1に設定します。- それ以外の場合、合計要素数が奇数なら
max(left1, left2)を返します。偶数なら、max(left1, left2) + min(right1, right2)を2で割った値をテキストとして返します。
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
落とし穴と境界ケース
- 浮動小数点数での半分の計算。Python は整数の中央値を
3.0と出力し、C の%fは 2.5 を2.500000と出力します。合計は整数のままにしておきましょう。 - 負の奇数の合計に対して、整数の商と
.5を書くこと。C と Java では-1 / 2は 0 となり、-0.5 に対して 0.5 が得られます。Python では-5 // 2は -3 となり、-2.5 に対して -3.5 が得られます。絶対値を半分にして、後から符号を付けましょう。 -0と書くこと。中央の値 -1 と 1 の合計は 0 で、答えは"0"です。合計から符号を取りましょう。- 長い方のリストを検索すること。
j = half-iは 0 未満になったり、nを超えたりすることがあります。まずリストを入れ替えましょう。 i = 0のときにnums1[i-1]を読み取ること。たとえば[9]と[1, 2]の場合です。値がない場合は無限大を使いましょう。
よくある質問3
2つのソート済み配列の中央値の時間計算量はどれくらいですか？
カットに対する二分探索は、短い方のリストで可能なカット数を各ステップで半分にするため、時間計算量は O(log(min(m, n)))、空間計算量は O(1) です。マージには O(m + n) かかります。3000個ずつの2つのリストなら、6000個に対して約12ステップです。
なぜ短い方の配列で二分探索を行うのですか？
j = half-i だからです。i が短い方のリストの範囲内にあれば、j は 0 から長い方のリストの長さまでの範囲に収まるため、すべての読み取りは範囲内にあるか、無限大として扱うリストの末尾を超えた位置になります。
浮動小数点数を使わずに中央値を返すにはどうすればよいですか？
中央の2つの値を整数として加算します。合計が偶数なら2で割ります。合計が奇数なら、その絶対値の半分を書き、.5を付けます。合計が負の場合はマイナス記号を付けます。-1は"-0.5"になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findMedianSortedArrays(nums1, nums2):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums1 = [1, 4] nums2 = [2, 7, 9]
期待される出力
"4"