Leetcode (4) - - trouver la médiane de deux tableaux ordonnés positifs

Leetcode（4）——Trouver la médiane de deux tableaux de séquence positive

Titre

Les deux tailles données sont $m$ Et $n$ Ordre positif de（De petit en grand）Tableau $nums1$ Et $nums2$.S'il vous plaît trouver et retourner ces deux tableaux d'ordre positif Médiane .

La complexité temporelle de l'algorithme devrait être $O(log(m+n))$.

Exemple 1：

Entrée：nums1 = [1,3], nums2 = [2]
Produits：2.00000
Explication：Fusionner les tableaux = [1,2,3] ,Médiane 2

Exemple 2：

Entrée：nums1 = [1,2], nums2 = [3,4]
Produits：2.50000
Explication：Fusionner les tableaux = [1,2,3,4] ,Médiane (2 + 3) / 2 = 2.5

Conseils：

• nums1.length == m
• nums2.length == n
• $0$ <= m <= $1000$
• $0$ <= n <= $1000$
• $1$ <= m + n <= $2000$
• $-10^6$ <= nums1[i], nums2[i] <= $10^6$

Explication du problème

Fusionner et trouver d'autres façons de ne pas écrire , Complexité temporelle insuffisante et simplicité

​​  Utiliser la fusion,Fusionner deux tableaux ordonnés,Obtenir un grand tableau ordonné.Éléments situés au milieu d'un grand tableau ordonné,Est la médiane.

• Il n'est pas nécessaire de fusionner deux tableaux ordonnés,Il suffit de trouver la position médiane.Comme la longueur des deux tableaux est connue,Par conséquent, la somme des indices des deux tableaux correspondant à la médiane est également connue.Maintenir deux pointeurs,Indice initial pointant vers deux tableaux $0$ Emplacement,Déplacez le pointeur vers une valeur plus petite à la fois（Si un pointeur a atteint la fin du tableau,Il suffit de déplacer le pointeur d'un autre tableau）,Jusqu'à la position médiane.
• Supposons que la longueur des deux tableaux ordonnés soit $m$ Et $n$,Quelle est la complexité de ces deux idées？

​​  La complexité temporelle de la première idée est $O(m+n)$,La complexité spatiale est $O(m+n)$.La deuxième idée, bien qu'elle puisse réduire la complexité spatiale à $O(1)$,Mais la complexité temporelle reste $O(m+n)$.

Méthode 1：Recherche binaire

Idées

​​  S'il y a une exigence de complexité temporelle $\log$,Il faut habituellement une recherche binaire,Cette question peut également être réalisée par une recherche binaire.

​​  Selon la définition de la médiane,Quand $m+n$ C'est un nombre impair,La médiane est la deuxième de deux tableaux ordonnés $(m+n+1)/2$ Éléments,Quand $m+n$ Quand c'est un nombre pair,La médiane est la deuxième de deux tableaux ordonnés $(m+n)/2$ Éléments et $(m+n)/2+1$ Moyenne des éléments.
​​  Donc,, Cette question peut se traduire par ： Cherchez la deuxième dans deux tableaux ordonnés $k$ Petit nombre,Quand $m+n$ C'est un nombre impair,$k$ Pour $(m+n)/2+1$,Quand $m+n$ Quand c'est un nombre pair,$k$ Pour $(m+n)/2$ Et $(m+n)/2+1$.

L'idée de l'algorithme spécifique est la suivante ：

​​  Supposons que les deux tableaux ordonnés soient $\text{A}$ Et $\text{B}$.Pour trouver $k$ Éléments,Nous pouvons comparer $\text{A}[k/2-1]$ Et $\text{B}[k/2-1]$,Parmi eux $/$ Représente la Division des entiers.
​​  Parce que $\text{A}[k/2-1]$ Et $\text{B}[k/2-1]$ DeDevant.Séparément. $\text{A}[0..k/2-2]$ Et $\text{B}[0..k/2-2]$,C'est - à - dire: $k/2-1$ Éléments,Pour $\text{A}[k/2-1]$ Et $\text{B}[k/2-1]$ Moins élevé de,Tout au plus. $(k/2-1)+(k/2-1)\le k-2$ Les éléments sont plus petits,Alors ça ne peut pas être la $k$ Un petit nombre.

C'est pourquoi nous Trois situations peuvent être résumées ：

• Si $\text{A}[k/2-1]<\text{B}[k/2-1]$,Que $\text{A}[k/2-1]$ Un nombre inférieur ou égal à au plus $\text{A}$ Avant $k/2-1$ Nombre et $\text{B}$ Avant $k/2-1$ Nombre,C'est - à - dire $\text{A}[k/2-1]$ Petit nombreLa plupartSeulement $k-2$ - Oui.,Donc, $\text{A}[k/2-1]$ Ce n'est pas possible. $k$ Nombre,$\text{A}[0]$ À $\text{A}[k/2-1]$ Ni l'un ni l'autre. $k$ Nombre,$\text{A}[0]$ À $\text{A}[k/2-1]$ Tout peut être exclu.
• Si $\text{A}[k/2-1]>\text{B}[k/2-1]$,EtPeut être exclu $\text{B}[0]$ À $\text{B}[k/2-1]$.
• Si $\text{A}[k/2-1]=\text{B}[k/2-1]$,Et Peut être classé dans le premier cas de traitement .

Je vois.,Comparaison $\text{A}[k/2-1]$ Et $\text{B}[k/2-1]$ Après,Peut être exclu $k/2$ C'est impossible. $k$ Petit nombre,La recherche a été réduite de moitié.En même temps,Nous La recherche binaire se poursuivra sur le nouveau tableau exclu ,Et selon le nombre que nous excluons,,Diminution $k$ Valeur de,C'est parce que nous n'excluons pas plus de $k$ Petit nombre.

Il y a trois situations qui nécessitent un traitement spécial：

• Si $\text{A}[k/2-1]$ Ou $\text{B}[k/2-1]$ Hors de portée,Nous pouvons alors choisir le dernier élément du tableau correspondant.Dans ce cas,,Nous devons réduire en fonction du nombre d'exclusions $k$ Valeur de,Au lieu de simplement $k$ Moins $k/2$.
• Si un tableau est vide,Description tous les éléments du tableau sont exclus,Nous pouvons retourner directement à la $k$ Petits éléments.
• Si $k=1$,Il suffit de retourner la valeur minimale des deux premiers éléments du tableau.

Exemple

Un exemple illustre l'algorithme ci - dessus.Supposons deux tableaux ordonnés comme suit:：

La longueur des deux tableaux ordonnés est $4$ Et $9$,La somme des longueurs est $13$,La médiane est la deuxième de deux tableaux ordonnés $7$ Éléments,Il faut donc trouver $k=7$ Éléments.

Comparer deux tableaux ordonnés avec un indice de $k/2-1=2$ Nombre de,C'est - à - dire: $\text{A}[2]$ Et $\text{B}[2]$,Comme indiqué ci - dessous：

Parce que $\text{A}[2]>\text{B}[2]$,Par conséquent, exclure $\text{B}[0]$ À $\text{B}[2]$,Tableau $\text{B}$ Offset de l'indice pour（offset）Devient $3$,Mise à jour simultanée $k$ Valeur de：$k=k-k/2=4$.

Recherche suivante,Comparer deux tableaux ordonnés avec un indice de $k/2-1=1$ Nombre de,C'est - à - dire: $\text{A}[1]$ Et $\text{B}[4]$,Comme indiqué ci - dessous,Où les crochets indiquent le nombre qui a été exclu.

Parce que $\text{A}[1]<\text{B}[4]$,Par conséquent, exclure $\text{A}[0]$ À $\text{A}[1]$,Tableau $\text{A}$ Le décalage de l'indice devient $2$,Mise à jour simultanée $k$ Valeur de：$k=k-k/2=2$.

Recherche suivante,Comparer deux tableaux ordonnés avec un indice de $k/2-1=0$ Nombre de,Comparaison $\text{A}[2]$ Et $\text{B}[3]$,Comme indiqué ci - dessous,Où les crochets indiquent le nombre qui a été exclu.

Parce que $\text{A}[2]=\text{B}[3]$,Selon les règles précédentes,Exclusion $\text{A}$ Éléments dans,Par conséquent, exclure $\text{A}[2]$,Tableau $\text{A}$ Le décalage de l'indice devient $3$,Mise à jour simultanée $k$ Valeur de： $k=k-k/2=1$.

Parce que $k$ La valeur de devient $1$,Comparez donc le premier nombre dans la gamme d'indices non exclus des deux tableaux ordonnés,Le plus petit de ces nombres est $k$ Nombre,Parce que $\text{A}[3]>\text{B}[3]$,Par conséquent, $k$ Oui. $\text{B}[3]=4$.

Mise en œuvre du Code

Leetcode Explication officielle：

class Solution {
    
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
    
        /* Principales idées：Pour trouver k (k>1) Petits éléments,Alors prends - le. pivot1 = nums1[k/2-1] Et pivot2 = nums2[k/2-1] Comparer * Ici. "/" Indique la Division * nums1 Petite et moyenne taille égale à pivot1 Les éléments de nums1[0 .. k/2-2] Total général k/2-1 - Oui. * nums2 Petite et moyenne taille égale à pivot2 Les éléments de nums2[0 .. k/2-2] Total général k/2-1 - Oui. * Prends - le. pivot = min(pivot1, pivot2),Inférieur ou égal à pivot Le total des éléments ne dépassera pas (k/2-1) + (k/2-1) <= k-2 - Oui. * Voilà. pivot Le plus grand en soi ne peut être que k-1 Petits éléments * Si pivot = pivot1,Alors nums1[0 .. k/2-1] Ça ne peut même pas être k Petits éléments.Prenez tous ces éléments "Supprimer",Le reste comme nouveau nums1 Tableau * Si pivot = pivot2,Alors nums2[0 .. k/2-1] Ça ne peut même pas être k Petits éléments.Prenez tous ces éléments "Supprimer",Le reste comme nouveau nums2 Tableau * Grâce à nous "Supprimer" Quelques éléments（Ces éléments sont plus importants que k Les petits éléments sont plus petits）,Des modifications sont donc nécessaires k Valeur de,Moins le nombre de suppressions */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
    
            // Situation aux frontières
            if (index1 == m)
                return nums2[index2 + k - 1];
            if (index2 == n)
                return nums1[index1 + k - 1];
            if (k == 1)
                return min(nums1[index1], nums2[index2]);

            // Situation normale
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
    
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            } else {
    
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1)
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        else
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
    }
};

Analyse de la complexité

Complexité temporelle：$O(log(m+n))$,Parmi eux $m$ Et $n$ Ce sont des tableaux ${\text{nums}}_1$ Et ${\text{nums}}_2$ Longueur.Au début, il y avait $k=(m+n)/2$ Ou $k=(m+n)/2+1$,Chaque cycle réduit de moitié la portée de la recherche,Donc la complexité temporelle est $O(\log (m+n))$.
Complexité spatiale：$O(1)$

Méthode 2：Recherche binaire+Tableau de partition

Idées

​​   Pour résoudre ce problème en utilisant la méthode de partition ,Besoin de compréhension「 Quel est le rôle de la médiane 」, Si le rôle de la Division médiane est compris , C'est proche de la réponse ..Dans les statistiques, La médiane est utilisée ：

Diviser un ensemble en deux sous - ensembles de longueur égale,Les éléments d'un sous - ensemble sont toujours plus grands que ceux d'un autre sous - ensemble.

Tout d'abord,,N'importe où $i$ Oui. $\text{A}$ Divisé en deux parties ：

Parce que $\text{A}$ Oui. $m$ Éléments, Donc il y a $m+1$ Méthode de division des espèces （$i\in [0,m]$）.

$\text{len}(\text{left\_A})=i,\text{len}(\text{right\_A})=m-i$
Attention!：Quand $i=0$ Heure,$\text{left\_A}$ Pour un ensemble vide, Et quand $i=m$ Heure, $\text{right\_A}$ Pour un ensemble vide.

De la même manière,N'importe où $j$ Oui. $\text{B}$ Divisé en deux parties ：

Oui. $\text{left\_A}$ Et $\text{left\_B}$ Dans une collection ,Et va $\text{right\_A}$ Et $\text{right\_B}$ Dans une autre collection . Et nommez ces deux nouvelles collections $\text{left\_part}$ Et $\text{right\_part}$：

Quand $\text{A}$ Et $\text{B}$ Lorsque la longueur totale est pair ,Si ça peut être confirmé：

• $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})$
• $\max (\text{left\_part})\le \min (\text{right\_part})$

Alors,$\{\text{A},\text{B}\}$ Tous les éléments ont été divisés en deux parties de même longueur , Et l'élément de la partie précédente est toujours inférieur ou égal à l'élément de la partie suivante . La médiane est la moyenne du maximum de la partie précédente et du minimum de la partie suivante. ：
$$\text{median}=\frac{\text{max}(\text{left}\_\text{part})+\text{min}(\text{right}\_\text{part})}{2}$$

Quand $\text{A}$ Et $\text{B}$ Lorsque la longueur totale est impaire ,Si ça peut être confirmé：

• $\text{len}(\text{left\_part})=\text{len}(\text{right\_part})+1$
• $\max (\text{left\_part})\le \min (\text{right\_part})$

Alors,$\{\text{A},\text{B}\}$ Tous les éléments ont été divisés en deux parties , La première partie a un élément de plus que la dernière , Et l'élément de la partie précédente est toujours inférieur ou égal à l'élément de la partie suivante . La médiane est la valeur maximale de la partie précédente ：
$$\text{median}=\text{max}(\text{left}\_\text{part})$$

La première condition est différente pour les longueurs totales égales et impaires , Mais les deux cas peuvent être combinés . La deuxième condition est la même pour les longueurs totales pair et impair .

Pour s'assurer que ces deux conditions ,Il suffit de garantir：

• $i+j=m-i+n-j$（Quand $m+n$ Même nombre）Ou $i+j=m-i+n-j+1$（Quand $m+n$ C'est un nombre impair）. Nombre d'éléments de la partie précédente à gauche du signe égal , Nombre d'éléments à droite du signe égal pour la dernière partie .Oui. $i$ Et $j$ Déplacez tout à gauche du signe égal ,Et nous aurons $i+j=\frac{m+n+1}{2}$. Le résultat de la fraction ici ne conserve que la partie entière .
• $0\le i\le m$,$0\le j\le n$. Si nous avions prévu $\text{A}$ Longueur inférieure ou égale à $\text{B}$ Longueur,C'est - à - dire: $m\le n$. Pour n'importe quel $i\in [0,m]$,Tous. $j=\frac{m+n+1}{2}-i\in [0,n]$,Alors, on est là. $[0,m]$ énumération dans le champ d'application de $i$ Et obtenir $j$, Il n'y a pas besoin de propriétés supplémentaires .
  • Si $\text{A}$ La longueur de, On va juste échanger $\text{A}$ Et $\text{B}$ C'est tout..
  • Si $m>n$, C'est tout. $j$ Ça pourrait être négatif.
• $\text{B}[j-1]\le \text{A}[i]$ Et $\text{A}[i-1]\le \text{B}[j]$, C'est - à - dire que la valeur maximale de la partie précédente est inférieure ou égale à la valeur minimale de la partie suivante .

Pour simplifier l'analyse,Hypothèses $\text{A}[i-1],\text{B}[j-1],\text{A}[i],\text{B}[j]$ Toujours présent.Pour $i=0$、$i=m$、$j=0$、$j=n$ Ces conditions critiques , Il suffit de préciser $\text{A}[-1]=\text{B}[-1]=-\infty$,$A[m]=\text{B}[n]=\infty$ C'est tout.. C'est aussi plus intuitif ： Lorsqu'un tableau n'apparaît pas dans la section précédente , La valeur correspondante est négative infinie , N'aurait pas d'effet sur la valeur maximale de la partie précédente ; Lorsqu'un tableau n'apparaît pas dans la dernière partie , La valeur correspondante est positive infinie , N'aurait pas d'effet sur la valeur minimale de cette dernière partie .

Ce qu'il nous faut, c'est：

In $[0,m]$ Trouvé dans $i$,De faire：
$\text{B}[j-1]\le \text{A}[i]$ Et $\text{A}[i-1]\le \text{B}[j]$,Parmi eux $j=\frac{m+n+1}{2}-i$

Nous avons prouvé que c'est équivalent à ：

In $[0,m]$ Le plus grand $i$,De faire：
$\text{A}[i-1]\le \text{B}[j]$,Parmi eux $j=\frac{m+n+1}{2}-i$

C'est parce que：

• Quand $i$ De $0\sim m$ Incrémental,$\text{A}[i-1]$ Incrémental,$\text{B}[j]$ Dégressif, Donc il doit y avoir un plus grand $i$ Satisfaction $\text{A}[i-1]\le \text{B}[j]$;
• Si $i$ C'est le plus grand.,Alors, ça veut dire $i+1$ Insatisfait.Oui. $i+1$ On peut obtenir $\text{A}[i]>\text{B}[j-1]$,C'est - à - dire $\text{B}[j-1]<\text{A}[i]$, Juste avant la transformation équivalente avec nous $i$ La nature de （ Encore mieux ）.

Pour qu'on puisse $i$ In $[0,m]$ Recherche binaire dans l'intervalle de , Trouver la plus grande satisfaction $\text{A}[i-1]\le \text{B}[j]$ De $i$ Valeur, On obtient la méthode de division .En ce moment, Diviser les valeurs maximales des éléments de la partie précédente , Et la plus petite des Parties suivantes de l'élément , C'est la médiane de ces deux tableaux. .

Mise en œuvre du Code

Leetcode Explication officielle：

class Solution {
    
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
        if (nums1.size() > nums2.size()) {
    
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        // median1：Valeur maximale de la partie précédente
        // median2：Valeur minimale pour cette dernière partie
        int median1 = 0, median2 = 0;

        while (left <= right) {
    
            // La partie précédente contient nums1[0 .. i-1] Et nums2[0 .. j-1]
            // Cette dernière partie contient nums1[i .. m-1] Et nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j Représente séparément nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
            int nums_i = (i == m ? INT_MAX : nums1[i]);
            int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
            int nums_j = (j == n ? INT_MAX : nums2[j]);

            if (nums_im1 <= nums_j) {
    
                median1 = max(nums_im1, nums_jm1);
                median2 = min(nums_i, nums_j);
                left = i + 1;
            } else {
    
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
};

Analyse de la complexité

Complexité temporelle：$O(\log \min (m,n)))$,Parmi eux $m$ Et $n$ Ce sont des tableaux ${\text{nums}}_1$ Et ${\text{nums}}_2$ Longueur. L'intervalle de recherche est $[0,m]$, La longueur de l'intervalle est réduite de moitié après chaque cycle .Alors...,Il suffit d'exécuter $\log m$ Sous - cycle. Parce que le nombre d'opérations par cycle est constant ,Donc la complexité temporelle est $O(\log m)$. Parce que nous pourrions avoir besoin d'échanger ${\text{nums}}_1$ Et ${\text{nums}}_2$ De faire $m\le n$ Et nous La recherche binaire n'a été effectuée que sur des tableaux plus courts ,Donc la complexité temporelle est $O(\log \min (m,n)))$.
Complexité spatiale：$O(1)$