Median of Two Sorted Arrays
Tu reçois deux listes d’entiers, nums1 et nums2, chacune triée par ordre croissant et contenant au moins une valeur. Renvoie la médiane de toutes leurs valeurs réunies, sous forme de texte.
Si le nombre total est impair, la médiane est la valeur du milieu, comme "4". S’il est pair, c’est la moyenne des deux valeurs du milieu, comme "2.5" ou "-0.5". Écris un nombre entier sans virgule, et zéro sous la forme "0", jamais "-0". Vise une complexité temporelle de O(log(min(m, n))).
Fonction
- nums1integer-array
- la première liste, triée de la plus petite à la plus grande
- nums2integer-array
- la deuxième liste, triée du plus petit au plus grand
- Renvoiestring
- la médiane de toutes les valeurs, sous forme de texte comme « 4 » ou « -2.5 »
Contraintes
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Les deux listes sont triées par ordre non décroissant, et les valeurs peuvent se répéter.
Exemples
- Entrée
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Sortie
- "4"
- Explication
- Ensemble, les valeurs sont 1, 2, 4, 7, 9. Cinq valeurs ont une valeur médiane, la troisième, qui est 4.
- Entrée
- nums1 = [1, 2]nums2 = [3, 4]
- Sortie
- "2.5"
- Explication
- Ensemble, les valeurs sont 1, 2, 3, 4. Les deux valeurs du milieu sont 2 et 3, leur somme est 5, et la moitié de 5 est 2.5.
- Entrée
- nums1 = [-7, -3]nums2 = [-2, 0]
- Sortie
- "-2.5"
- Explication
- Ensemble, les valeurs sont -7, -3, -2, 0. Les valeurs centrales -3 et -2 donnent une somme de -5, et la moitié de -5 est -2.5.
Pour aller plus loin
Peux-tu utiliser la même coupure pour trouver la k-ième plus petite valeur des deux listes, quel que soit k, en temps logarithmique ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Fusionner les deux listes permet de trouver la médiane en
O(m + n). Pour faire mieux, imagine la médiane comme une coupure : une ligne qui répartit lesm + nvaleurs en une moitié inférieure et une moitié supérieure de même taille.La moitié inférieure est composée d’un préfixe de
nums1et d’un préfixe denums2. Si elle prendivaleurs denums1, le nombre de valeurs prises dansnums2en découle. La partition est correcte lorsque la dernière valeur prise dans chaque liste n’est pas supérieure à la première valeur restante dans l’autre.Effectuez une recherche binaire sur
idans la liste la plus courte. Si la dernière valeur prise dansnums1est trop grande, prenez-en moins ; si la dernière valeur prise dansnums2est trop grande, prenez-en davantage. À la bonne coupure, la médiane provient de la plus grande valeur en dessous de la coupure et de la plus petite au-dessus. Additionnez ces deux entiers et divisez vous-même la somme par deux.
Solution
Fusionner les listes donne la médiane en O(m + n), mais la plupart des valeurs lues ne peuvent pas modifier la réponse. La médiane dépend uniquement de l’endroit où se situe la séparation entre la moitié inférieure et la moitié supérieure, et un nombre détermine cette séparation : combien de valeurs la moitié inférieure prend dans la liste la plus courte. La recherche binaire le trouve en O(log(min(m, n))) étapes.
Fusionner les deux listes
Intuition
Fusionnez les listes comme le fait le tri fusion, pour obtenir une seule liste triée merged. Avec total = m + n, additionnez merged[(total-1)/2] et merged[total/2], en utilisant la division entière. Si le total est impair, les deux valeurs sont la valeur centrale ; s’il est pair, ce sont les deux valeurs centrales. Ainsi, la moitié de leur somme correspond dans les deux cas à la médiane.
Même si vous vous arrêtez au milieu, les étapes de fusion parcourent plus de la moitié des valeurs, donc le temps d’exécution est de O(m + n).
Algorithme
- Fusionnez les listes dans
merged, en prenant toujours la plus petite valeur actuelle, puis le reste de la liste qui n’est pas épuisée. - Avec
total = m + n, additionnezmerged[(total-1)/2]etmerged[total/2]. - Renvoyez la moitié de la somme sous forme de texte : divisez une somme paire par 2 ; pour une somme impaire, écrivez le signe, la moitié de la valeur absolue et
.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])Recherche binaire sur la coupure
Intuition
Fais en sorte que la moitié inférieure contienne half = (m+n+1)/2 valeurs, soit une de plus lorsque le total est impair. Elle prend i valeurs au début de nums1 et j = half-i au début de nums2. La coupure est correcte si aucune valeur en dessous n’est supérieure à une valeur au-dessus. Chaque liste étant triée, il reste deux vérifications : left1 ≤ right2 et left2 ≤ right1, où left est la dernière valeur qu’une liste donne à la moitié inférieure et right la première qu’elle conserve. Un côté manquant équivaut à moins ou plus l’infini.
Si left1 > right2, i est trop grand ; si left2 > right1, il est trop petit. On effectue donc une recherche binaire de i entre 0 et m. Pour [1, 2] et [3, 4], i = 1 échoue car left2 = 3 > right1 = 2, et i = 2 convient : (2 + 3) / 2 = 2.5.
Algorithme
- Faites de
nums1la liste la plus courte ; posezhalf = (m+n+1)/2. - Effectuez une recherche binaire de
ientrelo = 0ethi = m, avecj = half-i. - Lisez
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]etright2 = nums2[j], en utilisant l’infini au-delà d’une extrémité. - Si
left1 > right2, définissezhi = i-1. Sileft2 > right1, définissezlo = i+1. - Sinon, si le total est impair, renvoyez
max(left1, left2). Si le total est pair, divisez par deuxmax(left1, left2) + min(right1, right2), en tant que texte.
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
Pièges et cas limites
- Division par deux avec des nombres à virgule flottante. Python affiche une médiane entière sous la forme
3.0, et%fde C affiche 2.5 sous la forme2.500000. Garde la somme sous forme d’entier. - Écrire le quotient entier et
.5pour une somme impaire négative.-1 / 2vaut 0 en C et en Java, ce qui donne 0.5 pour -0.5 ;-5 // 2vaut -3 en Python, ce qui donne -3.5 pour -2.5. Divise la valeur absolue par deux et rétablis le signe. - Écrire
-0. Les valeurs centrales -1 et 1 ont une somme de 0, et la réponse est"0". Prends le signe de la somme. - Rechercher dans la liste la plus longue.
j = half-ipeut être inférieur à 0 ou dépassern. Échange d’abord les listes. - Lire
nums1[i-1]lorsquei = 0, comme avec[9]et[1, 2]. Utilise des infinis pour les valeurs manquantes.
Questions fréquentes3
Quelle est la complexité temporelle de « Median of Two Sorted Arrays » ?
La recherche dichotomique sur la coupure prend O(log(min(m, n))) en temps et O(1) en espace, car chaque étape réduit de moitié les coupures possibles dans la liste la plus courte. La fusion prend O(m + n) : pour deux listes de 3000 éléments, environ 12 étapes contre 6000.
Pourquoi effectuer une recherche binaire sur le tableau le plus court ?
Parce que j = half-i. Avec i parcourant la liste la plus courte, j reste entre 0 et la longueur de la liste la plus longue, donc chaque lecture est dans les limites ou au-delà d’une extrémité que tu traites comme l’infini.
Comment renvoyer la médiane sans nombres à virgule flottante ?
Additionnez les deux valeurs du milieu en tant qu’entiers. Divisez une somme paire par 2. Pour une somme impaire, écrivez la moitié de sa valeur absolue et .5, avec un signe moins lorsque la somme est négative : -1 devient "-0.5".
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def findMedianSortedArrays(nums1, nums2):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
nums1 = [1, 4] nums2 = [2, 7, 9]
Résultat attendu
"4"