Median of Two Sorted Arrays
Du erhältst zwei Listen mit ganzen Zahlen, nums1 und nums2, die jeweils aufsteigend sortiert sind und mindestens einen Wert enthalten. Gib den Median aller Werte zusammen als Text zurück.
Bei einer ungeraden Gesamtanzahl ist der Median der mittlere Wert, zum Beispiel "4". Bei einer geraden Anzahl ist er der Durchschnitt der beiden mittleren Werte, zum Beispiel "2.5" oder "-0.5". Gib eine ganze Zahl ohne Dezimalpunkt und null als "0" aus, niemals als "-0". Strebe eine Laufzeit von O(log(min(m, n))) an.
Funktion
- nums1integer-array
- die erste Liste, vom kleinsten zum größten sortiert
- nums2integer-array
- die zweite Liste, sortiert vom kleinsten zum größten
- Gibt zurückstring
- der Median aller Werte, als Text wie "4" oder "-2.5"
Einschränkungen
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Beide Listen sind in nicht absteigender Reihenfolge sortiert, und Werte können mehrfach vorkommen.
Beispiele
- Eingabe
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Ausgabe
- "4"
- Erklärung
- Zusammen ergeben die Werte 1, 2, 4, 7, 9. Bei fünf Werten gibt es einen mittleren Wert, den dritten, nämlich 4.
- Eingabe
- nums1 = [1, 2]nums2 = [3, 4]
- Ausgabe
- "2.5"
- Erklärung
- Zusammen ergeben die Werte 1, 2, 3, 4. Die beiden mittleren Werte sind 2 und 3, ihre Summe ist 5, und die Hälfte von 5 ist 2,5.
- Eingabe
- nums1 = [-7, -3]nums2 = [-2, 0]
- Ausgabe
- "-2.5"
- Erklärung
- Zusammen ergeben die Werte -7, -3, -2, 0. Die mittleren Werte -3 und -2 ergeben zusammen -5, und die Hälfte von -5 ist -2.5.
Weiterführende Frage
Kannst du denselben Schnitt verwenden, um für jedes k den k-kleinsten Wert der beiden Listen in logarithmischer Zeit zu finden?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Durch das Zusammenführen der beiden Listen wird der Median in
O(m + n)gefunden. Um es besser zu machen, betrachte den Median als Schnitt: eine Linie, die allem + nWerte in eine untere und eine obere Hälfte gleicher Größe aufteilt.Die untere Hälfte ist ein Präfix von
nums1plus ein Präfix vonnums2. Wenn sieiWerte ausnums1enthält, ergibt sich daraus die Anzahl der Werte ausnums2. Die Trennstelle ist richtig, wenn der letzte entnommene Wert aus jeder Liste nicht größer ist als der erste verbleibende Wert der anderen Liste.Binäre Suche nach
iin der kürzeren Liste. Wenn der letzte ausnums1entnommene Wert zu groß ist, nimm weniger davon; wenn der letzte ausnums2entnommene Wert zu groß ist, nimm mehr davon. Beim richtigen Schnitt stammt der Median aus dem größten Wert unterhalb des Schnitts und dem kleinsten Wert oberhalb davon. Addiere diese beiden Ganzzahlen und halbiere die Summe selbst.
Lösung
Das Zusammenführen der Listen ergibt den Median in O(m + n), aber die meisten Werte, die dabei gelesen werden, können die Antwort nicht verändern. Der Median hängt nur davon ab, wo der Schnitt zwischen der unteren und der oberen Hälfte liegt, und eine Zahl bestimmt diesen Schnitt: wie viele Werte die untere Hälfte aus der kürzeren Liste übernimmt. Die binäre Suche findet sie in O(log(min(m, n))) Schritten.
Die beiden Listen zusammenführen
Idee
Führe die Listen wie bei Merge Sort zu einer sortierten Liste merged zusammen. Mit total = m + n addiere merged[(total-1)/2] und merged[total/2] unter Verwendung der Ganzzahldivision. Bei einer ungeraden Gesamtzahl sind beide der mittlere Wert, und bei einer geraden Gesamtzahl sind es die beiden mittleren Werte, daher ist die Hälfte der Summe in beiden Fällen der Median.
Selbst wenn du in der Mitte stoppst, durchlaufen die Merge-Schritte mehr als die Hälfte der Werte, daher beträgt die Laufzeit O(m + n).
Algorithmus
- Führe die Listen zu
mergedzusammen, wobei du immer den kleineren aktuellen Wert nimmst, und füge dann den Rest der verbleibenden Liste hinzu. - Addiere bei
total = m + nmerged[(total-1)/2]undmerged[total/2]. - Gib die Hälfte der Summe als Text zurück: Teile eine gerade Summe durch 2; schreibe bei einer ungeraden Summe das Vorzeichen, die Hälfte des Absolutwerts und
.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])Binäre Suche nach der Trennstelle
Idee
Die untere Hälfte enthält half = (m+n+1)/2 Werte, bei einer ungeraden Gesamtzahl den zusätzlichen Wert. Sie nimmt i Werte vom Anfang von nums1 und j = half-i vom Anfang von nums2. Der Schnitt ist richtig, wenn nichts darunter größer ist als irgendetwas darüber. Beide Listen sind sortiert, daher bleiben zwei Prüfungen: left1 ≤ right2 und left2 ≤ right1, wobei left der letzte Wert ist, den eine Liste der unteren Hälfte zuweist, und right der erste Wert, den sie behält. Eine fehlende Seite zählt als minus beziehungsweise plus unendlich.
Wenn left1 > right2, ist i zu groß; wenn left2 > right1, ist es zu klein. Also wird i binär zwischen 0 und m gesucht. Bei [1, 2] und [3, 4] scheitert i = 1 an left2 = 3 > right1 = 2, und i = 2 ist erfolgreich: (2 + 3) / 2 = 2.5.
Algorithmus
- Mache
nums1zur kürzeren Liste; setzehalf = (m+n+1)/2. - Führe eine binäre Suche nach
ivonlo = 0bishi = mdurch, mitj = half-i. - Lies
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]undright2 = nums2[j]; jenseits eines Endes gilt Unendlich. - Falls
left1 > right2, setzehi = i-1. Fallsleft2 > right1, setzelo = i+1. - Andernfalls gib bei einer ungeraden Gesamtzahl
max(left1, left2)zurück. Bei einer geraden Gesamtzahl halbieremax(left1, left2) + min(right1, right2)und gib das Ergebnis als Text zurück.
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
Stolperfallen und Grenzfälle
- Halbieren mit Fließkommazahlen. Python gibt einen ganzzahligen Median als
3.0aus, und%fin C gibt 2.5 als2.500000aus. Lass die Summe eine Ganzzahl bleiben. - Den ganzzahligen Quotienten und
.5für eine negative ungerade Summe schreiben.-1 / 2ergibt in C und Java 0, also 0.5 statt -0.5;-5 // 2ergibt in Python -3, also -3.5 statt -2.5. Halbiere den Absolutwert und füge das Vorzeichen wieder hinzu. -0schreiben. Die mittleren Werte -1 und 1 ergeben zusammen 0, und die Antwort lautet"0". Übernimm das Vorzeichen von der Summe.- Die längere Liste durchsuchen.
j = half-ikann kleiner als 0 sein odernüberschreiten. Vertausche zuerst die Listen. nums1[i-1]lesen, wenni = 0, wie bei[9]und[1, 2]. Verwende für fehlende Werte Unendlichkeitswerte.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität von Median of Two Sorted Arrays?
Die binäre Suche nach dem Schnitt benötigt O(log(min(m, n))) Zeit und O(1) Speicherplatz, da jeder Schritt die möglichen Schnitte in der kürzeren Liste halbiert. Das Zusammenführen benötigt O(m + n): bei zwei Listen mit jeweils 3000 Elementen etwa 12 Schritte statt 6000.
Warum binäre Suche im kürzeren Array?
Da j = half-i. Da i innerhalb der kürzeren Liste liegt, bleibt j zwischen 0 und der Länge der längeren Liste, sodass jeder Lesezugriff innerhalb des Bereichs liegt oder über ein Ende hinausgeht, das du als unendlich behandelst.
Wie gibst du den Median ohne Gleitkommazahlen zurück?
Addiere die beiden mittleren Werte als ganze Zahlen. Teile eine gerade Summe durch 2. Schreibe bei einer ungeraden Summe die Hälfte ihres Absolutbetrags und .5, bei einer negativen Summe mit einem Minuszeichen: -1 wird zu "-0.5".
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def findMedianSortedArrays(nums1, nums2):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
nums1 = [1, 4] nums2 = [2, 7, 9]
Erwartete Ausgabe
"4"