二分探索で 2 つのソート済み配列の中央値を求める - LeetCode 4

小さい順の 2 つの並びを 1 つにまとめずに、まとめたときの中央値を O(log(min(m, n))) で求めます。短い方の並びの「切る位置」を二分探索で探す練習です。

海外で定番の問題リスト 4 本のうち 2 本に入っています (NeetCode 150、LeetCode Top Interview 150)

問題

小さい順に並んだ整数の並び nums1 と nums2 を受け取ります。2 つを合わせて小さい順に並べたときの中央値を返す関数を書いてください。

  • 中央値は、合わせた個数が奇数なら真ん中の値、偶数なら真ん中の 2 つの平均です
  • 戻り値は数です。平均が小数になるときは 6.5 のように返します。ちょうど整数になるときは、6 と返しても 6.0 と返しても同じと見ます (例の出力は 6 と書きます)
  • nums1 と nums2 の長さはそれぞれ 0 以上 1000 以下で、合わせて 1 つ以上あります。値はどれも -1000000 以上 1000000 以下です
  • 長さを m と n として、2 つをまとめる O(m + n) ではなく、O(log(min(m, n))) で求めてください

入力と出力の例

例 1

合わせると [1, 2, 4, 6, 9] の 5 つで、真ん中は 4 です。

入力

nums1 = [1, 4, 9]
nums2 = [2, 6]

出力

4

例 2

合わせると [3, 5, 8, 10] の 4 つで、真ん中の 2 つは 5 と 8 です。平均は 6.5 です。

入力

nums1 = [3, 8]
nums2 = [5, 10]

出力

6.5

例 3

片方が空です。

入力

nums1 = []
nums2 = [7]

出力

7

図で見る

例 1 で、解き方がどう動くか。押すと大きく開きます。

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

  • 「ソート済みの配列が 2 つあります。まとめたときの中央値を求めてください」
  • 最初にまとめる書き方を出すと、「O(m + n) は分かりました。対数時間にできますか?」と一段下げるよう求められます
  • 書き終えたあとに「片方が空なら?」「なぜ短い方で探すのですか?」と、端の場合と理由を確かめられます

この問題は、二分探索で「値」ではなく「切る位置」を探す形です。何を探すのかを先に言葉にすると、条件を落としにくくなります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

  1. ヒント 2

  2. ヒント 3

  3. ヒント 4答えに近い

アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。

二分探索は、並んだデータの範囲を半分ずつ絞ります。100 万件でも 20 回ほどで 1 件になります。

main.py
def find_median(nums1: list[int], nums2: list[int]) -> float:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(find_median([1, 4, 9], [2, 6]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します