Median von zwei sortierten Arrays unterschiedlicher Größe
Bei zwei sortierten Arrays, a[] und b[], besteht die Aufgabe darin, den Median dieser sortierten Arrays in O(log n + log m) Zeitkomplexität zu finden, wenn n die Anzahl der Elemente im ersten Array ist, und m ist die Anzahl der Elemente im zweiten Array.
Dies ist eine Erweiterung des Medians von zwei sortierten Arrays gleicher Größe . Hier behandeln wir auch Arrays ungleicher Größe.
Beispiel:
Input: ar1[] = {-5, 3, 6, 12, 15}
ar2[] = {-12, -10, -6, -3, 4, 10}
Output : The median is 3.
Explanation : The merged array is :
ar3[] = {-12, -10, -6, -5 , -3,
3, 4, 6, 10, 12, 15},
So the median of the merged array is 3
Input: ar1[] = {2, 3, 5, 8}
ar2[] = {10, 12, 14, 16, 18, 20}
Output : The median is 11.
Explanation : The merged array is :
ar3[] = {2, 3, 5, 8, 10, 12, 14, 16, 18, 20}
if the number of the elements are even,
so there are two middle elements,
take the average between the two :
(10 + 12) / 2 = 11.
Methode 1: Diese Methode verwendet einen linearen und einfacheren Ansatz.
Ansatz: Die angegebenen Arrays sind sortiert, führen Sie also die sortierten Arrays auf effiziente Weise zusammen und behalten Sie die Anzahl der Elemente bei, die in das Ausgabearray oder das gedruckte Formular eingefügt wurden. Wenn also die Elemente im Ausgabearray halb so groß sind wie die ursprüngliche Größe des angegebenen Arrays, wird das Element als Medianelement ausgegeben. Es gibt zwei Fälle:
- Fall 1: m+n ist ungerade, der Median liegt bei (m+n)/2. Index in dem Array, das nach dem Zusammenführen beider Arrays erhalten wird.
- Fall 2: m+n ist gerade, der Median ist der Durchschnitt der Elemente am Index ((m+n)/2 – 1) und (m+n)/2 im Array, das nach dem Zusammenführen beider Arrays erhalten wird
Algorithmus:
- Gegeben sind zwei Arrays sortiert. Sie können also in O(m+n)-Zeit zusammengeführt werden. Erstellen Sie eine Variable count, um eine Anzahl von Elementen im Ausgabearray zu haben.
- Wenn der Wert von (m+n) ungerade ist, gibt es nur einen Median, sonst ist der Median der Durchschnitt der Elemente bei Index (m+n)/2 und ((m+n)/2 – 1).
- Um die beiden Arrays zusammenzuführen, lassen Sie zwei Indizes i und j anfangs 0 zugewiesen. Vergleichen Sie den i-ten Index des ersten Arrays und den j-ten Index des zweiten, erhöhen Sie den Index des kleinsten Elements und erhöhen Sie die Anzahl.
- Überprüfen Sie, ob die Zählung (m+n) / 2 erreicht hat, wenn (m+n) ungerade ist, und speichern Sie das Element, wenn gerade, speichern Sie den Durchschnitt von (m+n)/2-ten und (m+n)/2-1-ten Element und drucken Sie es aus.
Implementierung:
C++
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* This function returns median of ar1[] and ar2[].
Assumption in this function:
Both ar1[] and ar2[] are sorted arrays */
int getMedian(int ar1[], int ar2[], int n, int m)
{
int i = 0; /* Current index of input array ar1[] */
int j = 0; /* Current index of input array ar2[] */
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
//index is median i.e. (m+n)/2
if((m + n) % 2 == 1)
{
for (count = 0; count <= (n + m)/2; count++)
{
if(i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging ar1 and ar2
else
{
for (count = 0; count <= (n + m)/2; count++)
{
m2 = m1;
if(i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2)/2;
}
}
/* Driver code */
int main()
{
int ar1[] = {900};
int ar2[] = {5, 8, 10, 20};
int n1 = sizeof(ar1)/sizeof(ar1[0]);
int n2 = sizeof(ar2)/sizeof(ar2[0]);
cout << getMedian(ar1, ar2, n1, n2);
return 0;
}
// This is code is contributed by rathbhupendra
C
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
#include <stdio.h>
/* This function returns median of ar1[] and ar2[].
Assumption in this function:
Both ar1[] and ar2[] are sorted arrays */
int getMedian(int ar1[], int ar2[], int n, int m)
{
int i = 0; /* Current index of input array ar1[] */
int j = 0; /* Current index of input array ar2[] */
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
//index is median i.e. (m+n)/2
if((m + n) % 2 == 1) {
for (count = 0; count <= (n + m)/2; count++) {
if(i != n && j != m){
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n){
m1 = ar1[i++];
}
// for case when j<m,
else{
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging ar1 and ar2
else {
for (count = 0; count <= (n + m)/2; count++) {
m2 = m1;
if(i != n && j != m){
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n){
m1 = ar1[i++];
}
// for case when j<m,
else{
m1 = ar1[j++];
}
}
return (m1 + m2)/2;
}
}
/* Driver program to test above function */
int main()
{
int ar1[] = {900};
int ar2[] = {5, 8, 10, 20};
int n1 = sizeof(ar1)/sizeof(ar1[0]);
int n2 = sizeof(ar2)/sizeof(ar2[0]);
printf("%d", getMedian(ar1, ar2, n1, n2));
getchar();
return 0;
}
// This code is uploaded by Pratil
Java
// A Simple Merge based O(n) solution
// to find median of two sorted arrays
class GFG{
// Function to calculate median
static int getMedian(int ar1[], int ar2[],
int n, int m)
{
// Current index of input array ar1[]
int i = 0;
// Current index of input array ar2[]
int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
//index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
public static void main(String[] args)
{
int ar1[] = { 900 };
int ar2[] = { 5, 8, 10, 20 };
int n1 = ar1.length;
int n2 = ar2.length;
System.out.println(getMedian(ar1, ar2, n1, n2));
}
}
// This code is contributed by Yash Singhal
Python3
# A Simple Merge based O(n) solution to find # median of two sorted arrays """ This function returns median of ar1[] and ar2[]. Assumption in this function: Both ar1[] and ar2[] are sorted arrays """ def getMedian(ar1, ar2, n, m) : i = 0 # Current index of input array ar1[] j = 0 # Current index of input array ar2[] m1, m2 = -1, -1 # Since there are (n+m) elements, # There are following two cases # if n+m is odd then the middle # index is median i.e. (m+n)/2 if((m + n) % 2 == 1) : for count in range(((n + m) // 2) + 1) : if(i != n and j != m) : if ar1[i] > ar2[j] : m1 = ar2[j] j += 1 else : m1 = ar1[i] i += 1 elif(i < n) : m1 = ar1[i] i += 1 # for case when j<m, else : m1 = ar2[j] j += 1 return m1 # median will be average of elements # at index ((m + n)/2 - 1) and (m + n)/2 # in the array obtained after merging ar1 and ar2 else : for count in range(((n + m) // 2) + 1) : m2 = m1 if(i != n and j != m) : if ar1[i] > ar2[j] : m1 = ar2[j] j += 1 else : m1 = ar1[i] i += 1 elif(i < n) : m1 = ar1[i] i += 1 # for case when j<m, else : m1 = ar2[j] j += 1 return (m1 + m2)//2 # Driver code ar1 = [900] ar2 = [5, 8, 10, 20] n1 = len(ar1) n2 = len(ar2) print(getMedian(ar1, ar2, n1, n2)) # This code is contributed by divyesh072019
C#
// A Simple Merge based O(n) solution
// to find median of two sorted arrays
using System;
class GFG{
// Function to calculate median
static int getMedian(int []ar1, int []ar2,
int n, int m)
{
// Current index of input array ar1[]
int i = 0;
// Current index of input array ar2[]
int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
//index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
public static void Main(String[] args)
{
int []ar1 = { 900 };
int []ar2 = { 5, 8, 10, 20 };
int n1 = ar1.Length;
int n2 = ar2.Length;
Console.WriteLine(getMedian(ar1, ar2, n1, n2));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
// This function returns median of ar1[] and ar2[].
// Assumption in this function:
// Both ar1[] and ar2[] are sorted arrays
function getMedian(ar1, ar2, n, m)
{
// Current index of input array ar1[]
let i = 0;
// Current index of input array ar2[]
let j = 0;
let count;
let m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// For case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// Median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// For case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
let ar1 = [900];
let ar2 = [5, 8, 10, 20];
let n1 = ar1.length;
let n2 = ar2.length;
document.write(getMedian(ar1, ar2, n1, n2));
// This code is contributed by divyeshrabadiya07
</script>
Ausgabe
10
Komplexitätsanalyse:
- Zeitkomplexität: O(m + n).
Um beide Arrays zusammenzuführen, wird O(m+n) Zeit benötigt. - Raumkomplexität: O(1).
Es wird kein zusätzlicher Platz benötigt.
Effiziente Lösung:
Ansatz: Die Idee ist einfach, berechnen Sie den Median beider Arrays und verwerfen Sie eine Hälfte jedes Arrays.
Nun, es gibt einige grundlegende Eckfälle. Für Arraygröße kleiner oder gleich 2
Angenommen, es gibt zwei Arrays und die Größe beider Arrays ist größer als 2.
Finden Sie das mittlere Element des ersten Arrays und das mittlere Element des zweiten Arrays (das erste Array ist kleiner als das zweite), wenn das mittlere Element des kleineren Arrays kleiner als das zweite Array ist, dann kann gesagt werden, dass alle Elemente der ersten Hälfte des kleineren Arrays in der ersten Hälfte der Ausgabe (zusammengeführtes Array) sein werden. Reduzieren Sie also den Suchraum, indem Sie die erste Hälfte des kleineren Arrays und die zweite Hälfte des größeren Arrays ignorieren. Andernfalls ignorieren Sie die zweite Hälfte des kleineren Arrays und die erste Hälfte eines größeren Arrays.
Darüber hinaus gibt es grundlegendere Eckfälle:
- Wenn die Größe des kleineren Arrays 0 ist. Gibt den Median eines größeren Arrays zurück.
- wenn die Größe des kleineren Arrays 1 ist.
- Die Größe des größeren Arrays ist ebenfalls 1. Gibt den Median zweier Elemente zurück.
- Wenn die Größe des größeren Arrays ungerade ist. Nach dem Hinzufügen des Elements aus dem 2. Array ist es gleichmäßig, sodass der Median im Durchschnitt aus zwei mittleren Elementen besteht. Das Element aus dem kleineren Array beeinflusst also den Median genau dann, wenn es zwischen dem (m/2 – 1)-ten und dem (m/2 + 1)-ten Element des größeren Arrays liegt. Finden Sie also den Median zwischen den vier Elementen, dem Element des kleineren Arrays und dem (m/2)-ten, (m/2 – 1)-ten und (m/2 + 1)-ten Element eines größeren Arrays
- Wenn die Größe gerade ist, suchen Sie auf ähnliche Weise nach dem Median von drei Elementen, dem Element des kleineren Arrays und dem (m/2)-ten, (m/2 – 1)-ten Element eines größeren Arrays
- Wenn die Größe des kleineren Arrays 2 ist
- Wenn das größere Array auch zwei Elemente hat, finden Sie den Median von vier Elementen.
- Wenn das größere Array eine ungerade Anzahl von Elementen hat, dann ist der Median eines der folgenden 3 Elemente
- Mittleres Element eines größeren Arrays
- Max des ersten Elements eines kleineren Arrays und des Elements kurz vor der Mitte, dh M/2-1. Element in einem größeren Array
- Min des zweiten Elements des kleineren Arrays und des Elements
direkt nach der Mitte im größeren Array, dh M/2 + 1. Element im größeren Array
- Wenn das größere Array eine gerade Anzahl von Elementen hat, dann ist der Median eines der folgenden 4 Elemente
- Die beiden mittleren Elemente des größeren Arrays
- Max des ersten Elements des kleineren Arrays und des Elements kurz vor dem ersten mittleren Element des größeren Arrays, dh M/2 – 2. Element
- Min des zweiten Elements des kleineren Arrays und des Elements direkt nach dem zweiten mittleren Element des größeren Arrays, M/2 + 1. Element
Wie kann eine Hälfte jedes Arrays verworfen werden?
Nehmen wir ein Beispiel, um diese
Eingabe zu verstehen: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
brr[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19 }
Probelauf des Codes:
Rekursiver Aufruf 1:
kleineres Array[] = 1 2 3 4 5 6 7 8 9 10, mittleres = 5
größeres Array[] = 11 12 13 14 15 16 17 18 19 , Mitte = 155 < 15
Verwerfe die erste Hälfte des ersten Arrays und die zweite Hälfte des zweiten ArraysRekursiver Aufruf 2:
kleineres array[] = 11 12 13 14 15, mid = 13
größeres array[] = 5 6 7 8 9 10, mid = 77 < 13
Verwerfe die erste Hälfte des zweiten Arrays und die zweite Hälfte des ersten ArraysRekursiver Aufruf 3:
kleineres Array[] = 11 12 13 , mid = 12
größeres Array[] = 7 8 9 10 , mid = 88 < 12
Verwerfe die erste Hälfte des zweiten Arrays und die zweite Hälfte des ersten ArraysRekursiver Aufruf 4:
kleineres Array[] = 11 12
größeres Array[] = 8 9 10Die Größe des kleineren Arrays ist 2 und die Größe des größeren Arrays ist ungerade
, also ist der Median der Median von max( 11, 8), 9, min( 10, 12)
, also 9, 10, 11, also der Median ist 10.Ausgabe: 10.000000
Algorithmus:
- Erstellen Sie eine rekursive Funktion, die zwei Arrays und die Größen beider Arrays akzeptiert.
- Beachten Sie die Basisfälle für die Größe von Arrays kleiner als 2. (zuvor in Ansatz besprochen). Hinweis: Das erste Array ist immer das kleinere Array.
- Finden Sie die mittleren Elemente beider Arrays. dh Element bei (n – 1)/2 und (m – 1)/2 des ersten bzw. zweiten Arrays. Vergleichen Sie beide Elemente.
- Wenn das mittlere Element des kleineren Arrays kleiner als das mittlere Element des größeren Arrays ist, muss die erste Hälfte des kleineren Arrays unbedingt in der ersten Hälfte des zusammengeführten Arrays liegen. Es kann auch gesagt werden, dass es ein Element in der ersten Hälfte des größeren Arrays und in der zweiten Hälfte des kleineren Arrays gibt, das der Median ist. Reduzieren Sie also den Suchraum auf die erste Hälfte des größeren Arrays und die zweite Hälfte des kleineren Arrays.
- Wenn das mittlere Element des kleineren Arrays größer als das mittlere Element des größeren Arrays ist, reduzieren Sie den Suchraum auf die erste Hälfte des kleineren Arrays und die zweite Hälfte des größeren Arrays.
Implementierung:
C++
// A C++ program to find median of two sorted arrays of
// unequal sizes
#include <bits/stdc++.h>
using namespace std;
// A utility function to find median of two integers
float MO2(int a, int b)
{ return ( a + b ) / 2.0; }
// A utility function to find median of three integers
float MO3(int a, int b, int c)
{
return a + b + c - max(a, max(b, c))
- min(a, min(b, c));
}
// A utility function to find a median of four integers
float MO4(int a, int b, int c, int d)
{
int Max = max( a, max( b, max( c, d ) ) );
int Min = min( a, min( b, min( c, d ) ) );
return ( a + b + c + d - Max - Min ) / 2.0;
}
// Utility function to find median of single array
float medianSingle(int arr[], int n)
{
if (n == 0)
return -1;
if (n%2 == 0)
return (double)(arr[n/2] + arr[n/2-1])/2;
return arr[n/2];
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
float findMedianUtil( int A[], int N, int B[], int M )
{
// If smaller array is empty, return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1)
{
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M & 1)
return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3( B[M/2], B[M/2 - 1], A[0] );
}
// If the smaller array has two elements
else if (N == 2)
{
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M & 1)
return MO3 ( B[M/2],
max(A[0], B[M/2 - 1]),
min(A[1], B[M/2 + 1])
);
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4 ( B[M/2],
B[M/2 - 1],
max( A[0], B[M/2 - 2] ),
min( A[1], B[M/2 + 1] )
);
}
int idxA = ( N - 1 ) / 2;
int idxB = ( M - 1 ) / 2;
/* if A[idxA] <= B[idxB], then median must exist in
A[idxA....] and B[....idxB] */
if (A[idxA] <= B[idxB] )
return findMedianUtil(A + idxA, N/2 + 1, B, M - idxA );
/* if A[idxA] > B[idxB], then median must exist in
A[...idxA] and B[idxB....] */
return findMedianUtil(A, N/2 + 1, B + idxA, M - idxA );
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
float findMedian( int A[], int N, int B[], int M )
{
if (N > M)
return findMedianUtil( B, M, A, N );
return findMedianUtil( A, N, B, M );
}
// Driver program to test above functions
int main()
{
int A[] = {900};
int B[] = {5, 8, 10, 20};
int N = sizeof(A) / sizeof(A[0]);
int M = sizeof(B) / sizeof(B[0]);
printf("%f", findMedian( A, N, B, M ) );
return 0;
}
Java
// A Java program to find median of two sorted arrays of
// unequal sizes
import java.util.*;
class GFG {
// A utility function to find median of two integers
static float MO2(int a, int b) {
return (float) ((a + b) / 2.0);
}
// A utility function to find median of three integers
static float MO3(int a, int b, int c) {
return a + b + c - Math.max(a, Math.max(b, c)) -
Math.min(a, Math.min(b, c));
}
// A utility function to find a median of four integers
static float MO4(int a, int b, int c, int d) {
int Max = Math.max(a, Math.max(b, Math.max(c, d)));
int Min = Math.min(a, Math.min(b, Math.min(c, d)));
return (float) ((a + b + c + d - Max - Min) / 2.0);
}
// Utility function to find median of single array
static float medianSingle(int arr[], int n) {
if (n == 0)
return -1;
if (n % 2 == 0)
return (float) ((double) (arr[n / 2] +
arr[n / 2 - 1]) / 2);
return arr[n / 2];
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
static float findMedianUtil(int A[], int N, int B[], int M) {
// If smaller array is empty, return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1) {
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M % 2 == 1)
return MO2(B[M / 2], (int) MO3(A[0],
B[M / 2 - 1], B[M / 2 + 1]));
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3(B[M / 2], B[M / 2 - 1], A[0]);
}
// If the smaller array has two elements
else if (N == 2) {
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M % 2 == 1)
return MO3(B[M / 2], Math.max(A[0], B[M / 2 - 1]),
Math.min(A[1], B[M / 2 + 1]));
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4(B[M / 2], B[M / 2 - 1],
Math.max(A[0], B[M / 2 - 2]),
Math.min(A[1], B[M / 2 + 1]));
}
int idxA = (N - 1) / 2;
int idxB = (M - 1) / 2;
/*
* if A[idxA] <= B[idxB], then median
must exist in A[idxA....] and B[....idxB]
*/
if (A[idxA] <= B[idxB])
return findMedianUtil(Arrays.copyOfRange(A, idxA, A.length),
N / 2 + 1, B, M - idxA);
/*
* if A[idxA] > B[idxB], then median
must exist in A[...idxA] and B[idxB....]
*/
return findMedianUtil(A, N / 2 + 1,
Arrays.copyOfRange(B, idxB, B.length), M - idxA);
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
static float findMedian(int A[], int N, int B[], int M)
{
if (N > M)
return findMedianUtil(B, M, A, N);
return findMedianUtil(A, N, B, M);
}
// Driver program to test above functions
public static void main(String[] args)
{
int A[] = { 900 };
int B[] = { 5, 8, 10, 20 };
int N = A.length;
int M = B.length;
System.out.printf("%f", findMedian(A, N, B, M));
}
}
// This code is contributed by Princi Singh.
Python3
# A Python3 program to find median of two sorted arrays of
# unequal sizes
# A utility function to find median of two integers
def MO2(a, b) :
return ( a + b ) / 2
# A utility function to find median of three integers
def MO3(a, b, c) :
return a + b + c - max(a, max(b, c)) - min(a, min(b, c))
# A utility function to find a median of four integers
def MO4(a, b, c, d) :
Max = max( a, max( b, max( c, d ) ) )
Min = min( a, min( b, min( c, d ) ) )
return ( a + b + c + d - Max - Min ) / 2
# Utility function to find median of single array
def medianSingle(arr, n) :
if (n == 0) :
return -1
if (n % 2 == 0) :
return (arr[n / 2] + arr[n / 2 - 1]) / 2
return arr[n / 2]
# This function assumes that N is smaller than or equal to M
# This function returns -1 if both arrays are empty
def findMedianUtil(A, N, B, M) :
# If smaller array is empty, return median from second array
if (N == 0) :
return medianSingle(B, M)
# If the smaller array has only one element
if (N == 1) :
# Case 1: If the larger array also has one element,
# simply call MO2()
if (M == 1) :
return MO2(A[0], B[0])
# Case 2: If the larger array has odd number of elements,
# then consider the middle 3 elements of larger array and
# the only element of smaller array. Take few examples
# like following
# A = {9}, B[] = {5, 8, 10, 20, 30} and
# A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M & 1 != 0) :
return MO2( B[M / 2], MO3(A[0], B[M / 2 - 1], B[M / 2 + 1]) )
# Case 3: If the larger array has even number of element,
# then median will be one of the following 3 elements
# ... The middle two elements of larger array
# ... The only element of smaller array
return MO3(B[M // 2], B[M // 2 - 1], A[0])
# If the smaller array has two elements
elif (N == 2) :
# Case 4: If the larger array also has two elements,
# simply call MO4()
if (M == 2) :
return MO4(A[0], A[1], B[0], B[1])
# Case 5: If the larger array has odd number of elements,
# then median will be one of the following 3 elements
# 1. Middle element of larger array
# 2. Max of first element of smaller array and element
# just before the middle in bigger array
# 3. Min of second element of smaller array and element
# just after the middle in bigger array
if (M & 1 != 0) :
return MO3 (B[M / 2], max(A[0], B[M / 2 - 1]), min(A[1], B[M / 2 + 1]))
# Case 6: If the larger array has even number of elements,
# then median will be one of the following 4 elements
# 1) & 2) The middle two elements of larger array
# 3) Max of first element of smaller array and element
# just before the first middle element in bigger array
# 4. Min of second element of smaller array and element
# just after the second middle in bigger array
return MO4 (B[M / 2], B[M / 2 - 1], max( A[0], B[M / 2 - 2] ), min( A[1], B[M / 2 + 1] ))
idxA = ( N - 1 ) / 2
idxB = ( M - 1 ) / 2
''' if A[idxA] <= B[idxB], then median must exist in
A[idxA....] and B[....idxB] '''
if (A[idxA] <= B[idxB] ) :
return findMedianUtil(A + idxA, N / 2 + 1, B, M - idxA )
''' if A[idxA] > B[idxB], then median must exist in
A[...idxA] and B[idxB....] '''
return findMedianUtil(A, N / 2 + 1, B + idxA, M - idxA )
# A wrapper function around findMedianUtil(). This function
# makes sure that smaller array is passed as first argument
# to findMedianUtil
def findMedian(A, N, B, M) :
if (N > M) :
return findMedianUtil( B, M, A, N );
return findMedianUtil( A, N, B, M )
# Driver code
A = [900]
B = [5, 8, 10, 20]
N = len(A)
M = len(B)
print(findMedian(A, N, B, M ))
# This code is contributed by divyesh072019
C#
// A C# program to find median of two sorted arrays of
// unequal sizes
using System;
class GFG
{
// A utility function to find median of two integers
static float MO2(int a, int b)
{
return (float) ((a + b) / 2.0);
}
// A utility function to find median of three integers
static float MO3(int a, int b, int c)
{
return a + b + c - Math.Max(a, Math.Max(b, c)) -
Math.Min(a, Math.Min(b, c));
}
// A utility function to find a median of four integers
static float MO4(int a, int b, int c, int d)
{
int Max = Math.Max(a, Math.Max(b, Math.Max(c, d)));
int Min = Math.Min(a, Math.Min(b, Math.Min(c, d)));
return (float) ((a + b + c + d - Max - Min) / 2.0);
}
// Utility function to find median of single array
static float medianSingle(int[] arr, int n)
{
if (n == 0)
return -1;
if (n % 2 == 0)
return (float) ((double) (arr[n / 2] +
arr[n / 2 - 1]) / 2);
return arr[n / 2];
}
static int[] copyOfRange (int[] src, int start, int end)
{
int len = end - start;
int[] dest = new int[len];
Array.Copy(src, start, dest, 0, len);
return dest;
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
static float findMedianUtil(int[] A, int N,
int[] B, int M)
{
// If smaller array is empty,
// return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1)
{
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M % 2 == 1)
return MO2(B[M / 2], (int) MO3(A[0],
B[M / 2 - 1], B[M / 2 + 1]));
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3(B[M / 2], B[M / 2 - 1], A[0]);
}
// If the smaller array has two elements
else if (N == 2)
{
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M % 2 == 1)
return MO3(B[M / 2], Math.Max(A[0], B[M / 2 - 1]),
Math.Min(A[1], B[M / 2 + 1]));
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4(B[M / 2], B[M / 2 - 1],
Math.Max(A[0], B[M / 2 - 2]),
Math.Min(A[1], B[M / 2 + 1]));
}
int idxA = (N - 1) / 2;
int idxB = (M - 1) / 2;
/*
* if A[idxA] <= B[idxB], then median
must exist in A[idxA....] and B[....idxB]
*/
if (A[idxA] <= B[idxB])
return findMedianUtil(copyOfRange(A, idxA, A.Length),
N / 2 + 1, B, M - idxA);
/*
* if A[idxA] > B[idxB], then median
must exist in A[...idxA] and B[idxB....]
*/
return findMedianUtil(A, N / 2 + 1,
copyOfRange(B, idxB, B.Length), M - idxA);
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
static float findMedian(int[] A, int N, int[] B, int M)
{
if (N > M)
return findMedianUtil(B, M, A, N);
return findMedianUtil(A, N, B, M);
}
// Driver code
static void Main()
{
int[] A = { 900 };
int[] B = { 5, 8, 10, 20 };
int N = A.Length;
int M = B.Length;
Console.WriteLine(findMedian(A, N, B, M));
}
}
// This code is contributed by divyeshrabadiya07
PHP
<?php
// A PHP program to find median
// of two sorted arrays of
// unequal sizes
// A utility function to
// find median of two integers
function MO2($a, $b)
{
return ($a + $b) / 2.0;
}
// A utility function to
// find median of three integers
function MO3($a, $b, $c)
{
return $a + $b + $c -
max($a, max($b, $c)) -
min($a, min($b, $c));
}
// A utility function to find
// median of four integers
function MO4($a, $b, $c, $d)
{
$Max = max($a, max($b, max($c, $d)));
$Min = min($a, min($b, min( $c, $d)));
return ($a + $b + $c + $d - $Max - $Min) / 2.0;
}
// Utility function to
// find median of single array
function medianSingle($arr, $n)
{
if ($n == 0)
return -1;
if ($n % 2 == 0)
return ($arr[$n / 2] +
$arr[$n / 2 - 1]) / 2;
return $arr[$n / 2];
}
// This function assumes that N
// is smaller than or equal to M
// This function returns -1 if
// both arrays are empty
function findMedianUtil(&$A, $N, &$B, $M )
{
// If smaller array is empty,
// return median from second array
if ($N == 0)
return medianSingle($B, $M);
// If the smaller array
// has only one element
if ($N == 1)
{
// Case 1: If the larger
// array also has one
// element, simply call MO2()
if ($M == 1)
return MO2($A[0], $B[0]);
// Case 2: If the larger array
// has odd number of elements,
// then consider the middle 3
// elements of larger array and
// the only element of smaller
// array. Take few examples
// like following
// $A = array(9),
// $B = array(5, 8, 10, 20, 30)
// and $A = array(1),
// $B = array(5, 8, 10, 20, 30)
if ($M & 1)
return MO2($B[$M / 2], $MO3($A[0],
$B[$M / 2 - 1],
$B[$M / 2 + 1]));
// Case 3: If the larger array
// has even number of element,
// then median will be one of
// the following 3 elements
// ... The middle two elements
// of larger array
// ... The only element of
// smaller array
return MO3($B[$M / 2],
$B[$M / 2 - 1], $A[0]);
}
// If the smaller array
// has two elements
else if ($N == 2)
{
// Case 4: If the larger
// array also has two elements,
// simply call MO4()
if ($M == 2)
return MO4($A[0], $A[1],
$B[0], $B[1]);
// Case 5: If the larger array
// has odd number of elements,
// then median will be one of
// the following 3 elements
// 1. Middle element of
// larger array
// 2. Max of first element of
// smaller array and element
// just before the middle
// in bigger array
// 3. Min of second element
// of smaller array and element
// just after the middle
// in bigger array
if ($M & 1)
return MO3 ($B[$M / 2],
max($A[0], $B[$M / 2 - 1]),
min($A[1], $B[$M / 2 + 1]));
// Case 6: If the larger array
// has even number of elements,
// then median will be one of
// the following 4 elements
// 1) & 2) The middle two
// elements of larger array
// 3) Max of first element of
// smaller array and element
// just before the first middle
// element in bigger array
// 4. Min of second element of
// smaller array and element
// just after the second
// middle in bigger array
return MO4 ($B[$M / 2],
$B[$M / 2 - 1],
max($A[0], $B[$M / 2 - 2]),
min($A[1], $B[$M / 2 + 1]));
}
$idxA = ($N - 1 ) / 2;
$idxB = ($M - 1 ) / 2;
/* if $A[$idxA] <= $B[$idxB], then
median must exist in
$A[$idxA....] and $B[....$idxB] */
if ($A[$idxA] <= $B[$idxB] )
return findMedianUtil($A + $idxA,
$N / 2 + 1, $B,
$M - $idxA );
/* if $A[$idxA] > $B[$idxB],
then median must exist in
$A[...$idxA] and $B[$idxB....] */
return findMedianUtil($A, $N/2 + 1,
$B + $idxA, $M - $idxA );
}
// A wrapper function around
// findMedianUtil(). This
// function makes sure that
// smaller array is passed as
// first argument to findMedianUtil
function findMedian(&$A, $N,
&$B, $M )
{
if ($N > $M)
return findMedianUtil($B, $M,
$A, $N );
return findMedianUtil($A, $N,
$B, $M );
}
// Driver Code
$A = array(900);
$B = array(5, 8, 10, 20);
$N = sizeof($A);
$M = sizeof($B);
echo findMedian( $A, $N, $B, $M );
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// A Javascript program to find median of two sorted arrays of
// unequal sizes
// A utility function to find median of two integers
function MO2(a,b)
{
return ((a + b) / 2.0);
}
// A utility function to find median of three integers
function MO3(a, b, c)
{
return a + b + c - Math.max(a, Math.max(b, c)) -
Math.min(a, Math.min(b, c));
}
// A utility function to find a median of four integers
function MO4(a, b, c, d)
{
let Max = Math.max(a, Math.max(b, Math.max(c, d)));
let Min = Math.min(a, Math.min(b, Math.min(c, d)));
return ((a + b + c + d - Max - Min) / 2.0);
}
// Utility function to find median of single array
function medianSingle(arr, n)
{
if (n == 0)
return -1;
if (n % 2 == 0)
return ( (arr[n / 2] +
arr[n / 2 - 1]) / 2);
return arr[n / 2];
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
function findMedianUtil(A, N, B, M)
{
// If smaller array is empty, return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1) {
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M % 2 == 1)
return MO2(B[M / 2], MO3(A[0],
B[M / 2 - 1], B[M / 2 + 1]));
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3(B[M / 2], B[M / 2 - 1], A[0]);
}
// If the smaller array has two elements
else if (N == 2) {
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M % 2 == 1)
return MO3(B[M / 2], Math.max(A[0], B[M / 2 - 1]),
Math.min(A[1], B[M / 2 + 1]));
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4(B[M / 2], B[M / 2 - 1],
Math.max(A[0], B[M / 2 - 2]),
Math.min(A[1], B[M / 2 + 1]));
}
let idxA = (N - 1) / 2;
let idxB = (M - 1) / 2;
/*
* if A[idxA] <= B[idxB], then median
must exist in A[idxA....] and B[....idxB]
*/
if (A[idxA] <= B[idxB])
return findMedianUtil(A.slice(idxA, A.length),
N / 2 + 1, B, M - idxA);
/*
* if A[idxA] > B[idxB], then median
must exist in A[...idxA] and B[idxB....]
*/
return findMedianUtil(A, N / 2 + 1,
B.slice( idxB, B.length), M - idxA);
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
function findMedian(A,N,B,M)
{
if (N > M)
return findMedianUtil(B, M, A, N);
return findMedianUtil(A, N, B, M);
}
// Driver program to test above functions
let A = [ 900];
let B = [5, 8, 10, 20];
let N = A.length;
let M = B.length;
document.write(findMedian(A, N, B, M));
// This code is contributed by avanitrachhadiya2155
</script>
Ausgabe
10.000000
Komplexitätsanalyse:
- Zeitkomplexität: O(min(log m, log n)).
In jedem Schritt wird eine Hälfte jedes Arrays verworfen. Der Algorithmus benötigt also O(min(log m, log n)) Zeit, um den Medianwert zu erreichen. - Raumkomplexität: O(1).
Es wird kein zusätzlicher Platz benötigt.
Lösung 3: Einfacher mathematischer Ansatz
Ansatz : Die angegebenen zwei Arrays sind sortiert, also müssen wir sie mit der Methode System.arraycopy(src, srcPos, dest, destPos, length) zu einem dritten Array zusammenführen und dann das dritte Array mit der Methode Arrays.sort(array) sortieren .
1. Fall 1: Wenn die Länge des dritten Arrays ungerade ist, dann ist der Median bei (Länge)/2. Index in dem Array, das nach dem Zusammenführen beider Arrays erhalten wird.
2. Fall 2: Wenn die Länge des dritten Arrays gerade ist, dann ist der Median der Durchschnitt der Elemente am Index ((Länge)/2 ) und ((Länge)/2 – 1) in dem Array, das nach dem Zusammenführen beider erhalten wird die Arrays.
Algorithmus:
1. Merge the two given arrays into one array.
2. Then sort the third(merged) array
3. If the length of the third array is even then :
divide the length of array by 2
return arr[value] + arr[value - 1] / 2
4. If the length of the third array is odd then :
divide the length of array by 2
round that value
return the arr[value]
Implementierung:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int Solution(int arr[], int n)
{
// If length of array is even
if (n % 2 == 0)
{
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
int z = round(n / 2);
return arr[z];
}
}
// Driver Code
int main() {
// TODO Auto-generated method stub
int arr1[] = { -5, 3, 6, 12, 15 };
int arr2[] = { -12, -10, -6, -3, 4, 10 };
int i = sizeof(arr1) / sizeof(arr1[0]);
int j = sizeof(arr2) / sizeof(arr2[0]);
int arr3[i+j];
int l = i+j;
// Merge two array into one array
for(int k=0;k<i;k++)
{
arr3[k]=arr1[k];
}
int a=0;
for(int k=i;k<l;k++)
{
arr3[k]=arr2[a++];
}
// Sort the merged array
sort(arr3,arr3+l);
// calling the method
cout<<"Median = " << Solution(arr3, l);
}
// This code is contributed by SoumikMondal
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
public class GFG {
public static int Solution(int[] arr)
{
int n = arr.length;
// If length of array is even
if (n % 2 == 0)
{
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
int z = Math.round(n / 2);
return arr[z];
}
}
// Driver Code
public static void main(String[] args)
{
// TODO Auto-generated method stub
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
int i = arr1.length;
int j = arr2.length;
int[] arr3 = new int[i + j];
// Merge two array into one array
System.arraycopy(arr1, 0, arr3, 0, i);
System.arraycopy(arr2, 0, arr3, i, j);
// Sort the merged array
Arrays.sort(arr3);
// calling the method
System.out.print("Median = " + Solution(arr3));
}
}
// This code is contributed by Manas Tole
Python3
# Python3 program for the above approach
def Solution(arr):
n = len(arr)
# If length of array is even
if n % 2 == 0:
z = n // 2
e = arr[z]
q = arr[z - 1]
ans = (e + q) / 2
return ans
# If length of array is odd
else:
z = n // 2
ans = arr[z]
return ans
# Driver code
if __name__ == "__main__":
arr1 = [ -5, 3, 6, 12, 15 ]
arr2 = [ -12, -10, -6, -3, 4, 10 ]
# Concatenating the two arrays
arr3 = arr1 + arr2
# Sorting the resultant array
arr3.sort()
print("Median = ", Solution(arr3))
# This code is contributed by kush11
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
public static int Solution(int[] arr)
{
int n = arr.Length;
// If length of array is even
if (n % 2 == 0)
{
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
int z = n / 2;
return arr[z];
}
}
// Driver Code
static public void Main (){
// TODO Auto-generated method stub
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
// Merge two array into one array
var myList = new List<int>();
myList.AddRange(arr1);
myList.AddRange(arr2);
int[] arr3 = myList.ToArray();
// Sort the merged array
Array.Sort(arr3);
// calling the method
Console.Write("Median = " + Solution(arr3));
}
}
// This code is contributed by Shubhamsingh10
Javascript
<script>
// Javascript program for the above approach
function Solution(arr, n)
{
// If length of array is even
if (n % 2 == 0)
{
var z = n / 2;
var e = arr[z];
var q = arr[z - 1];
var ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
var z = Math.floor(n / 2);
return arr[z];
}
}
// Driver Code
// TODO Auto-generated method stub
var arr1 = [ -5, 3, 6, 12, 15 ];
var arr2 = [ -12, -10, -6, -3, 4, 10 ];
var i = arr1.length;
var j = arr2.length;
var l = i+j;
// Merge two array into one array
const arr3 = arr1.concat(arr2);
// Sort the merged array
arr3.sort(function(a, b) {
return a - b;
});
// calling the method
document.write("Median = " + Solution(arr3, l));
// This code is contributed by Shubham Singh
</script>
Ausgabe
Median = 3
Komplexitätsanalyse :
- Zeitkomplexität : O(n Log n)
- Raumkomplexität : O(i+j). Da wir ein neues Array der Größe i+j erstellen.
Lösung 4 :Binäre Suche
Ansatz: Die gegebenen zwei Arrays sind sortiert, sodass wir die Fähigkeit der binären Suche nutzen können, um das Array zu teilen und den Median zu finden.
Median bedeutet den Punkt, an dem das gesamte Array in zwei Teile geteilt wird. Da die beiden Arrays nicht zusammengeführt werden, müssen wir also zusammenführen, um den Median zu erhalten, was kostspielig ist. Anstatt zu verschmelzen, verwenden wir daher den unten angegebenen Algorithmus, um den Median effizient zu finden.
Algorithmus:
1. Lets assume that there are two arrays A and B with array A having the minimum number of elements.
If this is not the case than swap A and B to make A having small size.
2. The edge cases like one array is empty or both are empty will be handled.
3. let n be the size of A and m be the size of B.
Now think of an idea that if we have to find the median than we have to divide the whole merged array into two parts
namely left and right parts.
Now since we are given the size of left part (i.e (n+m+1)/2), Now look at below given example.
A-> 1,2,3,4,5 n = 5
B-> 1,2,3,4,5,6 m = 6
Here merged array will look like :- 1,1,2,2,3,3,4,4,5,5,6 and median then is 3
Now we can see our left part which is underlined. We divide A and B into two parts such that the
sum of left part of both A and B will result in left part of merged array.
A-> 1,2,3,4,5 // pointers l =0 and r = n-1 hence mid = (l+r)/2;
B -> 1,2,3,4,5,6
we can see that left part of A is given as n/2 and since total length of left part in merged array
is (m+n+1)/2, so left part of B = (m+n+1)/2-n/2;
Now we just have to confirm if our left and right partitions in A and B are correct or not.
4. Now we have 4 variables indicating four values two from array A and two from array B.
leftA -> Rightmost element in left part of A = 2
leftb -> Rightmost element in left part of B = 4
rightA -> Leftmost element in right part of A = 3
rightB -> Leftmost element in right part of B = 5
Hence to confirm that partition is correct we have to check the following conditions.
leftA<=rightB and leftB<=rightA // This is the case when the sum of two parts of A and B results in left part of merged array
if our partition not works that means we have to find other mid point in A and then left part in B
This is seen when
leftA > rightB //means we have to dec size of A's partition
so do r = mid-1;
else
do l =mid+1;
Hence repeat the above steps with new partitions till we get the answers.
5. If leftA<=rightB and leftB<=rightA
then we get correct partition and our answer depends on the total size of merged array (i.e. m+n)
If (m+n)%2==0
ans is max(leftA,leftB)+min(rightA,rightB)/2; // max of left part is nearest to median and min of right part is nearest to medain
else
ans is max(leftA,leftB);
Daher kann der obige Algorithmus codiert werden als
C++
#include <bits/stdc++.h>
using namespace std;
// Method to find median
double Median(vector<int>& A, vector<int>& B)
{
int n = A.size();
int m = B.size();
if (n > m)
return Median(B, A); // Swapping to make A smaller
int start = 0;
int end = n;
int realmidinmergedarray = (n + m + 1) / 2;
while (start <= end) {
int mid = (start + end) / 2;
int leftAsize = mid;
int leftBsize = realmidinmergedarray - mid;
int leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: INT_MIN; // checking overflow of indices
int leftB
= (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
int rightA
= (leftAsize < n) ? A[leftAsize] : INT_MAX;
int rightB
= (leftBsize < m) ? B[leftBsize] : INT_MAX;
// if correct partition is done
if (leftA <= rightB and leftB <= rightA) {
if ((m + n) % 2 == 0)
return (max(leftA, leftB)
+ min(rightA, rightB))
/ 2.0;
return max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
int main()
{
vector<int> arr1 = { -5, 3, 6, 12, 15 };
vector<int> arr2 = { -12, -10, -6, -3, 4, 10 };
cout << "Median of the two arrays are" << endl;
cout << Median(arr1, arr2);
return 0;
}
Java
public class GFG {
// Method to find median
static double Median(int[] A, int[] B)
{
int n = A.length;
int m = B.length;
if (n > m)
return Median(B, A); // Swapping to make A smaller
int start = 0;
int end = n;
int realmidinmergedarray = (n + m + 1) / 2;
while (start <= end) {
int mid = (start + end) / 2;
int leftAsize = mid;
int leftBsize = realmidinmergedarray - mid;
int leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: Integer.MIN_VALUE; // checking overflow of indices
int leftB
= (leftBsize > 0) ? B[leftBsize - 1] : Integer.MIN_VALUE;
int rightA
= (leftAsize < n) ? A[leftAsize] : Integer.MAX_VALUE;
int rightB
= (leftBsize < m) ? B[leftBsize] : Integer.MAX_VALUE;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return (Math.max(leftA, leftB)
+ Math.min(rightA, rightB))
/ 2.0;
return Math.max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
public static void main(String[] args) {
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
System.out.println("Median of the two arrays are");
System.out.println(Median(arr1, arr2));
}
}
// This code is contributed by Hritik
Python3
class Solution:
# Method to find median
def Median(self, A, B):
# Assumption both A and B cannot be empty
n = len(A)
m = len(B)
if (n > m):
return self.Median(B, A) # Swapping to make A smaller
start = 0
end = n
realmidinmergedarray = (n + m + 1) // 2
while (start <= end):
mid = (start + end) // 2
leftAsize = mid
leftBsize = realmidinmergedarray - mid
# checking overflow of indices
leftA = A[leftAsize - 1] if (leftAsize > 0) else float('-inf')
leftB = B[leftAsize - 1] if (leftBsize > 0) else float('-inf')
rightA = A[leftAsize] if (leftAsize < n) else float('inf')
rightB = A[leftAsize] if (leftBsize < m) else float('inf')
# if correct partition is done
if leftA <= rightB and leftB <= rightA:
if ((m + n) % 2 == 0):
return (max(leftA, leftB) + min(rightA, rightB)) / 2.0
return max(leftA, leftB)
elif (leftA > rightB):
end = mid - 1
else:
start = mid + 1
# Driver code
ans = Solution()
arr1 = [-5, 3, 6, 12, 15]
arr2 = [-12, -10, -6, -3, 4, 10]
print("Median of the two arrays is {}".format(ans.Median(arr1, arr2)))
# This code is contributed by Arpan
Ausgabe
Median der beiden Arrays sind 3
Zeitkomplexität: O(min(log m, log n)): Da die binäre Suche auf das kleinere der 2 Arrays angewendet wird Hilfsraum
: O(1)
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .