Alle Herausforderungen
Schwierig 1 gelöst 100.0% Erfolgsquote

Median of Two Sorted Arrays

Find the median of two sorted lists combined.

Das lernst du

  • Zwei sortierte Arrays per binärer Suche partitionieren
  • Den Median in O(log n) finden
  • Gerade und ungerade Gesamtlängen behandeln

Problem

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.

Einschränkungen

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

Beispiele

Beispiel 1
Eingabe:
first = [1, 3]
second = [2]

Erwartete Ausgabe:
expected = 2.0
Eingabe:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};

Erwartete Ausgabe:
double expected = 2.0;
Eingabe:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};

Erwartete Ausgabe:
double expected = 2.0;

Erläuterung

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

Beispiel 2
Eingabe:
first = [1, 2]
second = [3, 4]

Erwartete Ausgabe:
expected = 2.5
Eingabe:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};

Erwartete Ausgabe:
double expected = 2.5;
Eingabe:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};

Erwartete Ausgabe:
double expected = 2.5;

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Die gemeinsame Reihenfolge ist wichtig, aber du musst nicht alles mergen, wenn du die mittlere Trennung direkt findest.

Hinweis 2

Suche nach einer Partition, bei der die linken Hälften genau die unteren mittleren Elemente enthalten und jeder linke Wert nicht größer ist als jeder rechte.

Hinweis 3

Behandle leere Arrays sowie ungerade und gerade Gesamtlängen sorgfältig, da der Median aus einem oder zwei mittleren Werten kommen kann.

Erwartete Komplexität

Zeit O(log(min(m, n))), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 825 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.