すべてのチャレンジ
難しい 1件解決済み 正答率100.0%

Median of Two Sorted Arrays

Find the median of two sorted lists combined.

このチャレンジで学べること

  • Partition two sorted arrays with binary search
  • Find the median in O(log n)
  • Handle even and odd total lengths

問題

翻訳を表示

Both lists are sorted in ascending order. Find the median of all their numbers together; for an even count it is the average of the two middle values. An O(log(m + n)) partition search is possible, but any correct method within the limits is accepted.

Implement median_of_two(first, second).

Input

first: A sorted list. second: A sorted list.

Output

Return the median.

制約

0 ≤ lengths ≤ 100,000; the combined length is at least 1

例

例 1
入力:
first = [1, 3]
second = [2]

期待される出力:
expected = 2.0
入力:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};

期待される出力:
double expected = 2.0;
入力:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};

期待される出力:
double expected = 2.0;

解説

Combined: [1, 2, 3]; the middle value is 2.

例 2
入力:
first = [1, 2]
second = [3, 4]

期待される出力:
expected = 2.5
入力:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};

期待される出力:
double expected = 2.5;
入力:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};

期待される出力:
double expected = 2.5;

解説

Combined: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

The combined order matters, but you do not need to merge everything if you can find the middle split directly.

ヒント 2

Search for a partition where left halves contain exactly the lower middle elements and every left value is no larger than every right value.

ヒント 3

Handle empty arrays and both odd and even total lengths carefully, since the median may come from one middle value or two.

目安の計算量

O(log(min(m, n))) time, O(1) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 825 ms - 5/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。