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)))
Spis treści
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?
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)
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
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
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
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:
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!!
