给定两个排序数组a[]和b[]，任务是在时间复杂度为O（logn+logm）的情况下，当n是第一个数组中的元素数，m是第二个数组中的元素数时，找到这些排序数组的中值。 这是 两个大小相等的排序数组的中值 问题这里我们也处理大小不等的数组。
null
例子：
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 3Input: 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.
方法1： 该方法使用线性且更简单的方法。
方法： 给定的数组被排序，所以 以有效的方式合并已排序的数组 并保留插入到输出数组或打印表单中的元素数。因此，当输出数组中的元素是给定数组的原始大小的一半时，将该元素作为中间元素打印。有两种情况：
- 案例1： m+n是奇数，中位数在合并两个数组后获得的数组中的（m+n）/2个索引处。
- 案例2： m+n是偶数，中位数将是合并两个数组后获得的数组中索引（（m+n）/2–1）和（m+n）/2处元素的平均值
算法：
- 给定两个数组进行排序。所以它们可以在O（m+n）时间内合并。创建一个变量count，以便在输出数组中对元素进行计数。
- 如果（m+n）的值是奇数，那么只有一个中位数，其他中位数是指数（m+n）/2和（（m+n）/2–1处元素的平均值。
- 要合并这两个数组，请保持两个索引i和j最初指定为0。比较第一个数组的第i个索引和第二个数组的第j个索引，增加最小元素的索引并增加计数。
- 存储（m+n）/ 2和（m+n）/2-1在两个变量（在下面的C++代码中，M1和M2用于此目的）。
- 检查计数是否达到（m+n）/2。如果（m+n）是奇数返回m1，如果是偶数返回（m1+m2）/2。
实施：
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; /*loop till (m+n)/2*/ for (count = 0; count <= (m + n)/2; count++) { //store (n+m)/2-1 in m2 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++]; } } // 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 // other wise 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 if ((m + n) % 2 == 1){ return m1; } else { 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); } // This is code is contributed by rathbhupendra, modified by rajesh999 |
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> |
输出
10
复杂性分析：
- 时间复杂性： O（m+n）。 要合并两个数组，需要O（m+n）时间。
- 空间复杂性： O（1）。 不需要额外的空间。
高效的解决方案：
方法： 这个想法很简单，计算两个数组的中值，然后丢弃每个数组的一半。 现在，有一些基本的角落案例。对于小于或等于2的数组大小
假设有两个数组，且两个数组的大小都大于2。 找到第一个数组的中间元素和第二个数组的中间元素（第一个数组小于第二个数组），如果较小数组的中间元素小于第二个数组，则可以说较小数组的前半部分的所有元素都将位于输出的前半部分（合并数组）。因此，通过忽略较小数组的前半部分和较大数组的后半部分来减少搜索空间。否则忽略较小数组的后半部分和较大数组的前半部分。
除此之外，还有更基本的情况：
- 如果较小数组的大小为0。返回较大数组的中值。
- 如果较小数组的大小为1。
- 较大阵列的大小也是1。返回两个元素的中间值。
- 如果较大数组的大小为奇数。然后在添加第二个数组中的元素后，它将是偶数，因此中间值将是两个中间元素的平均值。因此，当且仅当较小数组的元素位于较大数组的（m/2–1）个元素和（m/2+1）个元素之间时，较小数组的元素才会影响中位数。所以，找到四个元素之间的中间值，较小数组的元素和较大数组的（m/2）th、（m/2–1）th和（m/2+1）th元素
- 同样，如果大小为偶数，则检查三个元素的中值，较小数组的元素和较大数组的（m/2）第（m/2–1）个元素
- 如果较小数组的大小为2
- 如果较大的数组也有两个元素，则找到四个元素的中间值。
- 如果较大的数组有奇数个元素，则中值将是以下3个元素之一
- 较大数组的中间元素
- 较小数组的第二个元素和中间元素之前的元素的最大值，即较大数组中的M/2-1个元素
- 较小数组和元素的第一个元素的最小值 就在较大数组的中间之后，即较大数组中的M/2+1元素
- 如果较大的数组有偶数个元素，则中值将是以下4个元素之一
- 较大数组的中间两个元素
- 较小数组中第一个元素和较大数组中第一个中间元素之前的元素的最大值，即M/2–第二个元素
- 较小数组中第二个元素的最小值，以及较大数组中第二个中间元素之后的元素，M/2+1个元素
如何丢弃每个阵列的一半？
让我们举个例子来理解这一点 输入： arr[]={1,2,3,4,5,6,7,8,9,10}， brr[]={11,12,13,14,15,16,17,18,19} 代码的试运行： 递归调用1： 较小的数组[]=12345678910，中间=5 更大的数组[]=1113141516171819，mid=15
5 < 15 丢弃第一个数组的前半部分和第二个数组的后半部分
递归调用2： 较小的数组[]=11131415，mid=13 更大的数组[]=5 6 7 8 9 10，mid=7
7 < 13 丢弃第二个数组的前半部分和第一个数组的后半部分
递归调用3： 较小的数组[]=11 12 13，mid=12 更大的数组[]=7 8 9 10，mid=8
8 < 12 丢弃第二个数组的前半部分和第一个数组的后半部分
递归调用4： 较小的数组[]=11 12 更大的数组[]=8 9 10
较小数组的大小为2，较大数组的大小为奇数 所以，中位数将是最大值（11，8），9，最小值（10，12）的中位数 这是9，10，11，所以中位数是10。
输出： 10
算法：
- 创建一个递归函数，该函数接受两个数组以及两个数组的大小。
- 对于小于2的阵列，请注意基本情况。（之前在方法中讨论过）。注意：第一个数组总是较小的数组。
- 找到两个数组的中间元素。i、 e元素分别位于第一和第二阵列的（n-1）/2和（m-1）/2处。比较两种元素。
- 如果较小数组的中间元素小于较大数组的中间元素，则较小数组的前半部分必须严格位于合并数组的前半部分。也可以说，在较大数组的前半部分和较小数组的后半部分中有一个元素，即中值。因此，将搜索空间缩小到较大数组的前半部分和较小数组的后半部分。
- 类似地，如果较小数组的中间元素大于较大数组的中间元素，则将搜索空间缩小到较小数组的前半部分和较大数组的后半部分。
实施：
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> |
输出
10.000000
复杂性分析：
- 时间复杂性： O（最小值（对数m，对数n））。 在每个步骤中，每个阵列的一半都会被丢弃。因此，该算法需要O（min（logm，logn））时间来达到中值。
- 空间复杂性： O（1）。 不需要额外的空间。
解决方案3： 简单数学方法
方法 ：给定的两个数组已排序，因此我们需要使用方法系统将它们合并为第三个数组。arraycopy（src、srcPos、dest、destPos、length），然后使用数组对第三个数组进行排序。排序（数组）方法。
1.情况1：如果第三个数组的长度为奇数，则中值位于合并两个数组后获得的数组的（长度）/2次索引处。
2.情况2：如果第三个数组的长度为偶数，则中值将是合并两个数组后获得的数组中索引（（长度）/2）和（（长度）/2–1）处元素的平均值。
算法：
1. Merge the two given arrays into one array.2. Then sort the third(merged) array3. 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]
实施：
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> |
输出
Median = 3
复杂性分析 :
- 时间复杂性 ：O（（n+m）对数（n+m））
- 空间复杂性 ：O（n+m）。因为我们正在创建一个大小为n+m的新数组。
解决方案4 : 二进制搜索
方法： 将给定的两个数组进行排序，这样我们就可以利用二进制搜索的能力来分割数组并找到中值。
中位数是指整个阵列被分成两部分的点。因此，由于两个阵列没有合并，因此为了获得中值，我们需要合并，这是非常昂贵的。因此，我们将使用下面给出的算法来高效地找到中值，而不是合并。
算法：
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 then 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);
因此，上述算法可以编码为
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[leftBsize - 1 ] if (leftBsize > 0 ) else float ( '-inf' ) rightA = A[leftAsize] if (leftAsize < n) else float ( 'inf' ) rightB = B[leftBsize] 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 |
C#
using System; 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] : Int32.MinValue; // checking overflow of indices int leftB = (leftBsize > 0) ? B[leftBsize - 1] : Int32.MinValue; int rightA = (leftAsize < n) ? A[leftAsize] : Int32.MaxValue; int rightB = (leftBsize < m) ? B[leftBsize] : Int32.MaxValue; // 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() { int [] arr1 = { -5, 3, 6, 12, 15 }; int [] arr2 = { -12, -10, -6, -3, 4, 10 }; Console.WriteLine( "Median of the two arrays are" ); Console.WriteLine(Median(arr1, arr2)); } } // This code is contributed by Shubham Singh |
Javascript
<script> // JavaScript Program to implement // the above approach // Method to find median function Median(A, B) { let n = A.length; let m = B.length; if (n > m) return Median(B, A); // Swapping to make A smaller let start = 0; let end = n; let realmidinmergedarray = Math.floor((n + m + 1) / 2); while (start <= end) { let mid = Math.floor((start + end) / 2); let leftAsize = mid; let leftBsize = realmidinmergedarray - mid; let leftA = (leftAsize > 0) ? A[leftAsize - 1] : Number.MIN_VALUE; // checking overflow of indices let leftB = (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN; let rightA = (leftAsize < n) ? A[leftAsize] : INT_MAX; let rightB = (leftBsize < m) ? B[leftBsize] : INT_MAX; // if correct partition is done if (leftA <= rightB && leftB <= rightA) { if ((m + n) % 2 == 0) return Math.floor((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 let arr1 = [-5, 3, 6, 12, 15]; let arr2 = [-12, -10, -6, -3, 4, 10]; document.write( "Median of the two arrays are" + "<br>" ); document.write(Median(arr1, arr2)) // This code is contributed by Potta Lokesh </script> |
输出
Median of the two arrays are3
时间复杂性： O（min（logm，logn））：因为二进制搜索应用于两个数组中较小的一个 辅助空间： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
