Mediana dwóch posortowanych tablic

Poziom trudności Ciężko
Często zadawane pytania Adobe Amazonka Apple Bloomberg ByteDance Facebook Goldman Sachs Google Microsoft Chcieć
Szyk Wyszukiwanie binarne Dziel i rządźodwiedzajacy 80

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Biorąc pod uwagę dwie posortowane tablice A i B o rozmiarze odpowiednio n i m. Znajdź medianę ostatecznego sortowania szyk otrzymane po scaleniu danych dwóch tablic lub innymi słowy, mówimy, że znajdź medianę dwóch posortowanych tablic.

(Oczekiwana złożoność czasowa: O (log (n)))

Podejście 1 dla mediany z dwóch posortowanych tablic

Używając metody z dwoma wskaźnikami, utwórz scaloną posortowaną tablicę A i B.

Następnie po prostu znajdź medianę tej tablicy.

Program C ++ dla mediany dwóch posortowanych tablic

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int k=n+m;                   // size of merged sorted array
    int M[k];                   // array which will store integers of A and B in ascending order
    int i=0,j=0,in=0;          // i is a pointer index for A
                              // j is a pointer index for B 
                             // in is a pointer index for M
    while(i<n || j<m){
        if(i<n && j<m){
            if(A[i]<B[j]){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        else{
            if(i<n){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        in++;
    }
    if(k%2==0){
        double m1 = M[k/2];
        double m2 = M[(k/2)-1];
        return (m1+m2)/2;
    }
    else{
        double m1 = M[k/2];
        return m1;
    }
    return -1;    
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
5 5
6 1 2 7 8
3 4 5 6 7
3.5

Analiza złożoności

Złożoność czasowa: O (max (n, m), ponieważ łączymy posortowaną tablicę przy użyciu obu tablic.

Złożoność przestrzeni: O (n + m), ponieważ przechowujemy ostateczną scaloną tablicę, która doprowadzi nas do złożoności przestrzeni O (n + m).

Podejście 2 dla mediany z dwóch posortowanych tablic

Aby rozwiązać ten problem, musimy najpierw zrozumieć, co właściwie robi mediana.

Jest to podział zbioru na dwa podzbiory o równej długości, tak że jeden podzbiór jest większy od drugiego.

tj. podziel zbiór na dwa podzbiory w taki sposób, że każdy element jednego podzbioru jest większy niż każdy element drugiego podzbioru.

Wróćmy teraz do problemu, musimy znaleźć medianę dwóch posortowanych tablic.

Czy możemy znaleźć partycję dla tablicy A i B, tak aby długość podzbiorów uzyskanych przez dodanie lewej i prawej strony obu partycji była równa?

Mediana dwóch posortowanych tablicszpilka

 

Dzielenie tablicy na i-tym miejscu oznacza również liczbę elementów z tej tablicy, które są obecne w lewym podzbiorze.

A jak wiemy, długość otrzymanych podzbiorów powinna być więc równa

przegroda A + przegroda B = (długość (A) + długość (B) +1) / 2

(Jeśli długość końcowej scalonej posortowanej tablicy jest nieparzysta, lewy podzbiór będzie miał więcej elementów)

Teraz pozostaje tylko sprawdzić, jak podzielić dane dwie tablice tak, aby prawy podzbiór był większy niż lewy podzbiór.

Zdefiniujmy idealną partycję posortowanych tablic:

Powiedzmy, że mamy tablicę A (długość n) i tablicę B (długość m)

Mediana dwóch posortowanych tablicszpilka

 

W takim razie podzieliliśmy A na i i B na j

Idealna partycja jest wtedy, gdy:

  • i + j = (n + m + 1) / 2 (podzbiory mają jednakową długość)
  • A [i-1] <= B [j] (elementy A po lewej stronie i pojawią się w lewym podzbiorze)
  • B [j-1] <= A [i] (elementy B po lewej stronie j pojawią się w lewym podzbiorze)

Jeśli A [i-1]> B [j] oznacza to, że po lewej stronie partycji A znajdują się elementy, które należy umieścić w większym (prawym) podzbiorze. W takim przypadku przesuniemy i w lewo, a j w prawo.

Jeśli B [j-1]> A [i] oznacza to, że po lewej stronie partycji B znajdują się elementy, które należy umieścić w większym (prawym) podzbiorze. W takim przypadku przesuniemy j w lewo i i w prawo.

Teraz, aby przenieść nasze wskaźniki partycji, możemy użyć wyszukiwania binarnego.

Wyjaśnienie

Zrozummy to na przykładzie:

Biorąc pod uwagę dwie posortowane tablice A i B.

Zacznijmy partycjonowanie A za pomocą wyszukiwania binarnego i sprawdźmy, czy możemy uzyskać idealną partycję, czy nie.

Krok 1

left = 0

right = 6

mid = (0 + 6) / 2 = 3 (podział na A)

Możemy otrzymać partycję B używając partycji A + partycji B = (długość (A) + długość (B) +1) / 2

partycjaB = (6 + 4 + 1) / 2 - partycja A.

partycja B = 5-3 = 2

szpilka

Lewa część partycji B jest większa niż prawa partycji A. Oznacza to, że musimy dodać więcej elementów A, aby uzyskać idealną partycję.

Krok 2

Czy po lewej = środek + 1, czyli po lewej = 4

right = 6

stąd nowy środek = (4 + 6) / 2 = 5

partycjaB = (6 + 4 + 1) / 2 - partycja A.

partycjaB = 0

szpilka

Lewa strona partycji A jest większa niż prawa partycji B. Oznacza to, że powinniśmy dodać więcej elementów B, aby uzyskać idealną partycję.

Krok 3

Zrób w prawo = środek 1

Lewy = 4

prawo = 4

stąd nowy środek = (4 + 4) / 2 = 4

partycjaB = (6 + 4 + 1) / 2 - partycja A.

partycjaB = 1

szpilka

Teraz widzimy, że na załączonym rysunku jest łącznie 5 elementów, a poza nim łącznie 5 elementów.

Ponadto lewa część partycji A jest mniejsza niż prawa partycji B.

A lewa część partycji B jest mniejsza niż prawa partycji A.

Stąd nasza tablica będzie się łączyć w ten sposób:

szpilka

Ponieważ nasza tablica ma równy rozmiar, mediana zostanie obliczona jako średnia z dwóch środkowych elementów końcowej posortowanej tablicy:

  • Jedną będzie maksimum z lewej strony idealnej partycji, tj. Max (17,11).
  • Drugim będzie minimum prawej strony idealnego podziału, czyli min (19,18).

Czyż nie

Uzyskana mediana = (17 + 18) / 2

= 17.5

Jeśli długość scalonej posortowanej tablicy jest nieparzysta, to odpowiedzią będzie po prostu maksimum lewej strony idealnej partycji.

Przykład

Wejście:

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i m, oznaczające rozmiar tablicy A i B.

Następny wiersz zawiera n liczb całkowitych oddzielonych spacjami, które oznaczają A [i], gdzie 0 <= i

Następny wiersz zawiera m liczb całkowitych oddzielonych spacjami, które oznaczają B [i], gdzie 0 <= i

Wyjście:

Wydrukuj medianę z podanych dwóch posortowanych tablic.

Program C ++ dla mediany dwóch posortowanych tablic

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int left = 0, right = n;
    while (left <= right) {
        int partitionA = (left + right)/2;
        int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2

        //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
        double maxLeftA = INT_MIN;
        if(partitionA > 0){
            maxLeftA = A[partitionA-1];
        }
            
        //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
        double minRightA = INT_MAX;
        if(partitionA < n){
            minRightA = A[partitionA];
        }
        
        //Similarly for maxLeftB and minrightB
        double maxLeftB = INT_MIN;
        if(partitionB > 0){
            maxLeftB = B[partitionB-1];
        }
            
        double minRightB = INT_MAX;
        if(partitionB < m){
            minRightB = B[partitionB];
        }
        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
            if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2;
            } 
            else {
                return max(maxLeftA, maxLeftB);
            }
        } 
        else if (maxLeftA > minRightB) {                          //move left side.
            right = partitionA - 1;
        }
        else {                                                   // move right side
            left = partitionA + 1;
        }
    }
    return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
4 5
1 2 7 8
3 4 5 6 7
5

Program JAVA dla mediany dwóch posortowanych tablic

import java.util.Scanner;
public class Main{
    public static double findMedian(int A[], int B[],int n,int m) {
        int left = 0, right = n;
        while (left <= right) {
            int partitionA = (left + right)/2;
            int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2
            //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
            double maxLeftA = Integer.MIN_VALUE;
            if(partitionA > 0){
                maxLeftA = A[partitionA-1];
            }
                
            //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
            double minRightA = Integer.MAX_VALUE;
            if(partitionA < n){
                minRightA = A[partitionA];
            }
                
            //Similarly for maxLeftB and minrightB
            double maxLeftB = Integer.MIN_VALUE;
            if(partitionB > 0){
                maxLeftB = B[partitionB-1];
            }
                    
            double minRightB = Integer.MAX_VALUE;
            if(partitionB < m){
                minRightB = B[partitionB];
            }
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
                if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                    return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2;
                } 
                else {
                    return Math.max(maxLeftA, maxLeftB);
                }
            } 
            else if (maxLeftA > minRightB) {                          //move left side.
                right = partitionA - 1;
            }
            else {                                                   // move right side
                left = partitionA + 1;
            }
        }
        return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
    }
        
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n,m;
        n = scan.nextInt();
        m = scan.nextInt();
        int A[]=new int[n];
        int B[]=new int[m];
        for(int i=0;i<n;i++){
            A[i] = scan.nextInt();
        }
        for(int i=0;i<m;i++){
            B[i] = scan.nextInt();
        }
        double median = findMedian(A,B,n,m);
        System.out.println(median);  
    }
}
4 6
6 7 8 9
1 2 3 4 5 6
5.5

Analiza złożoności dla mediany dwóch posortowanych tablic

Złożoność czasowa: O (log (n))

tak jak na każdym kroku zmniejszamy przestrzeń wyszukiwania o połowę (wybierając lewą lub prawą przestrzeń wyszukiwania ze środkowego indeksu).

Złożoność przestrzeni: O (1) ponieważ używamy tylko niektórych zmiennych do obliczeń.

Dziękuje za przeczytanie!!

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »