一、说明
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
二、解决方案参考
1. Swift 语言
// 方式一
class Solution {
func findMedianSortedArrays(nums1: [Int], _ nums2: [Int]) -> Double {
let m = nums1.count
let n = nums2.count
if m > n {
return findMedianSortedArrays(nums2, nums1)
}
var halfLength: Int = (m + n + 1) >> 1
var b = 0, e = m
var maxOfLeft = 0
var minOfRight = 0
while b <= e {
let mid1 = (b + e) >> 1
let mid2 = halfLength - mid1
if mid1 > 0 && mid2 < n && nums1[mid1 - 1] > nums2[mid2] {
e = mid1 - 1
} else if mid2 > 0 && mid1 < m && nums1[mid1] < nums2[mid2 - 1] {
b = mid1 + 1
} else {
if mid1 == 0 {
maxOfLeft = nums2[mid2 - 1]
} else if mid2 == 0 {
maxOfLeft = nums1[mid1 - 1]
} else {
maxOfLeft = max(nums1[mid1 - 1], nums2[mid2 - 1])
}
if (m + n) % 2 == 1 {
return Double(maxOfLeft)
}
if mid1 == m {
minOfRight = nums2[mid2]
} else if mid2 == n {
minOfRight = nums1[mid1]
} else {
minOfRight = min(nums1[mid1], nums2[mid2])
}
break
}
}
return Double(maxOfLeft + minOfRight) / 2.0
}
}
// 方式二
class MedianTwoSortedArrays {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
let m = nums1.count
let n = nums2.count
return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2
}
private func findKth(_ nums1: [Int], _ nums2: [Int], _ index: Int) -> Double {
let m = nums1.count
let n = nums2.count
guard m <= n else {
return findKth(nums2, nums1, index)
}
guard m != 0 else {
return Double(nums2[index - 1])
}
guard index != 1 else {
return Double(min(nums1[0], nums2[0]))
}
let i = min(index / 2, m)
let j = min(index / 2, n)
if nums1[i - 1] < nums2[j - 1] {
return findKth(Array(nums1[i..<m]), nums2, index - i)
} else {
return findKth(nums1, Array(nums2[j..<n]), index - j)
}
}
}2. Python 语言
// 方式一
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
a, b = sorted((nums1, nums2), key=len)
m, n = len(a), len(b)
after = (m + n - 1) / 2
lo, hi = 0, m
while lo < hi:
i = (lo + hi) / 2
if after-i-1 < 0 or a[i] >= b[after-i-1]:
hi = i
else:
lo = i + 1
i = lo
nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0
// 方式二
def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.03. Java 语言
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j-1] > A[i]){
iMin = iMin + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = iMax - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}4. C++ 语言
#include <stdio.h>
// Classical binary search algorithm, but slightly different
// if cannot find the key, return the position where can insert the key
int binarySearch(int A[], int low, int high, int key){
while(low<=high){
int mid = low + (high - low)/2;
if (key == A[mid]) return mid;
if (key > A[mid]){
low = mid + 1;
}else {
high = mid -1;
}
}
return low;
}
/tes:
// I feel the following methods is quite complicated, it should have a better high clear and readable solution
double findMedianSortedArrayHelper(int A[], int m, int B[], int n, int lowA, int highA, int lowB, int highB) {
// Take the A[middle], search its position in B array
int mid = lowA + (highA - lowA)/2;
int pos = binarySearch(B, lowB, highB, A[mid]);
int num = mid + pos;
// If the A[middle] in B is B's middle place, then we can have the result
if (num == (m+n)/2){
// If two arrays total length is odd, just simply return the A[mid]
// Why not return the B[pos] instead ?
// suppose A={ 1,3,5 } B={ 2,4 }, then mid=1, pos=1
// suppose A={ 3,5 } B={1,2,4}, then mid=0, pos=2
// suppose A={ 1,3,4,5 } B={2}, then mid=1, pos=1
// You can see, the `pos` is the place A[mid] can be inserted, so return A[mid]
if ((m+n)%2==1){
return A[mid];
}
// If tow arrys total length is even, then we have to find the next one.
int next;
// If both `mid` and `pos` are not the first postion.
// Then, find max(A[mid-1], B[pos-1]).
// Because the `mid` is the second middle number, we need to find the first middle number
// Be careful about the edge case
if (mid>0 && pos>0){
next = A[mid-1]>B[pos-1] ? A[mid-1] : B[pos-1];
}else if(pos>0){
next = B[pos-1];
}else if(mid>0){
next = A[mid-1];
}
return (A[mid] + next)/2.0;
}
// if A[mid] is in the left middle place of the whole two arrays
//
// A(len=16) B(len=10)
// [................] [...........]
// ^ ^
// mid=7 pos=1
//
// move the `low` pointer to the "middle" position, do next iteration.
if (num < (m+n)/2){
lowA = mid + 1;
lowB = pos;
if ( highA - lowA > highB - lowB ) {
return findMedianSortedArrayHelper(A, m, B, n, lowA, highA, lowB, highB);
}
return findMedianSortedArrayHelper(B, n, A, m, lowB, highB, lowA, highA);
}
// if A[mid] is in the right middle place of the whole two arrays
if (num > (m+n)/2) {
highA = mid - 1;
highB = pos-1;
if ( highA - lowA > highB - lowB ) {
return findMedianSortedArrayHelper(A, m, B, n, lowA, highA, lowB, highB);
}
return findMedianSortedArrayHelper(B, n, A, m, lowB, highB, lowA, highA);
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
//checking the edge cases
if ( m==0 && n==0 ) return 0.0;
//if the length of array is odd, return the middle one
//if the length of array is even, return the average of the middle two numbers
if ( m==0 ) return n%2==1 ? B[n/2] : (B[n/2-1] + B[n/2])/2.0;
if ( n==0 ) return m%2==1 ? A[m/2] : (A[m/2-1] + A[m/2])/2.0;
//let the longer array be A, and the shoter array be B
if ( m > n ){
return findMedianSortedArrayHelper(A, m, B, n, 0, m-1, 0, n-1);
}
return findMedianSortedArrayHelper(B, n, A, m, 0, n-1, 0, m-1);
}
int main()
{
int r1[] = {1};
int r2[] = {2};
int n1 = sizeof(r1)/sizeof(r1[0]);
int n2 = sizeof(r2)/sizeof(r2[0]);
printf("Median is 1.5 = %f
", findMedianSortedArrays(r1, n1, r2, n2));
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45, 50};
n1 = sizeof(ar1)/sizeof(ar1[0]);
n2 = sizeof(ar2)/sizeof(ar2[0]);
printf("Median is 17 = %f
", findMedianSortedArrays(ar1, n1, ar2, n2));
int ar11[] = {1, 12, 15, 26, 38};
int ar21[] = {2, 13, 17, 30, 45 };
n1 = sizeof(ar11)/sizeof(ar11[0]);
n2 = sizeof(ar21)/sizeof(ar21[0]);
printf("Median is 16 = %f
", findMedianSortedArrays(ar11, n1, ar21, n2));
int a1[] = {1, 2, 5, 6, 8 };
int a2[] = {13, 17, 30, 45, 50};
n1 = sizeof(a1)/sizeof(a1[0]);
n2 = sizeof(a2)/sizeof(a2[0]);
printf("Median is 10.5 = %f
", findMedianSortedArrays(a1, n1, a2, n2));
int a10[] = {1, 2, 5, 6, 8, 9, 10 };
int a20[] = {13, 17, 30, 45, 50};
n1 = sizeof(a10)/sizeof(a10[0]);
n2 = sizeof(a20)/sizeof(a20[0]);
printf("Median is 9.5 = %f
", findMedianSortedArrays(a10, n1, a20, n2));
int a11[] = {1, 2, 5, 6, 8, 9 };
int a21[] = {13, 17, 30, 45, 50};
n1 = sizeof(a11)/sizeof(a11[0]);
n2 = sizeof(a21)/sizeof(a21[0]);
printf("Median is 9 = %f
", findMedianSortedArrays(a11, n1, a21, n2));
int a12[] = {1, 2, 5, 6, 8 };
int a22[] = {11, 13, 17, 30, 45, 50};
n1 = sizeof(a12)/sizeof(a12[0]);
n2 = sizeof(a22)/sizeof(a22[0]);
printf("Median is 11 = %f
", findMedianSortedArrays(a12, n1, a22, n2));
int b1[] = {1 };
int b2[] = {2,3,4};
n1 = sizeof(b1)/sizeof(b1[0]);
n2 = sizeof(b2)/sizeof(b2[0]);
printf("Median is 2.5 = %f
", findMedianSortedArrays(b1, n1, b2, n2));
return 0;
}5. C 语言
#include <stdio.h>
#include <stdlib.h>
static double find_kth(int a[], int alen, int b[], int blen, int k)
{
/* Always assume that alen is equal or smaller than blen */
if (alen > blen) {
return find_kth(b, blen, a, alen, k);
}
if (alen == 0) {
return b[k - 1];
}
if (k == 1) {
return a[0] < b[0] ? a[0] : b[0];
}
/* Divide k into two parts */
int ia = k / 2 < alen ? k / 2 : alen;
int ib = k - ia;
if (a[ia - 1] < b[ib - 1]) {
/* a[ia - 1] must be ahead of k-th */
return find_kth(a + ia, alen - ia, b, blen, k - ia);
} else if (a[ia - 1] > b[ib - 1]) {
/* b[ib - 1] must be ahead of k-th */
return find_kth(a, alen, b + ib, blen - ib, k - ib);
} else {
return a[ia - 1];
}
}
static double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
int half = (nums1Size + nums2Size) / 2;
if ((nums1Size + nums2Size) & 0x1) {
return find_kth(nums1, nums1Size, nums2, nums2Size, half + 1);
} else {
return (find_kth(nums1, nums1Size, nums2, nums2Size, half) + find_kth(nums1, nums1Size, nums2, nums2Size, half + 1)) / 2;
}
}
int main(int argc, char **argv)
{
int r1[] = {1};
int r2[] = {2};
int n1 = sizeof(r1)/sizeof(r1[0]);
int n2 = sizeof(r2)/sizeof(r2[0]);
printf("Median is 1.5 = %f
", findMedianSortedArrays(r1, n1, r2, n2));
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45, 50};
n1 = sizeof(ar1)/sizeof(ar1[0]);
n2 = sizeof(ar2)/sizeof(ar2[0]);
printf("Median is 17 = %f
", findMedianSortedArrays(ar1, n1, ar2, n2));
int ar11[] = {1, 12, 15, 26, 38};
int ar21[] = {2, 13, 17, 30, 45 };
n1 = sizeof(ar11)/sizeof(ar11[0]);
n2 = sizeof(ar21)/sizeof(ar21[0]);
printf("Median is 16 = %f
", findMedianSortedArrays(ar11, n1, ar21, n2));
int a1[] = {1, 2, 5, 6, 8 };
int a2[] = {13, 17, 30, 45, 50};
n1 = sizeof(a1)/sizeof(a1[0]);
n2 = sizeof(a2)/sizeof(a2[0]);
printf("Median is 10.5 = %f
", findMedianSortedArrays(a1, n1, a2, n2));
int a10[] = {1, 2, 5, 6, 8, 9, 10 };
int a20[] = {13, 17, 30, 45, 50};
n1 = sizeof(a10)/sizeof(a10[0]);
n2 = sizeof(a20)/sizeof(a20[0]);
printf("Median is 9.5 = %f
", findMedianSortedArrays(a10, n1, a20, n2));
int a11[] = {1, 2, 5, 6, 8, 9 };
int a21[] = {13, 17, 30, 45, 50};
n1 = sizeof(a11)/sizeof(a11[0]);
n2 = sizeof(a21)/sizeof(a21[0]);
printf("Median is 9 = %f
", findMedianSortedArrays(a11, n1, a21, n2));
int a12[] = {1, 2, 5, 6, 8 };
int a22[] = {11, 13, 17, 30, 45, 50};
return 0;
}
--------------------------------------
版权声明：本文为【PythonJsGo】博主的原创文章，转载请附上原文出处链接及本声明。
博主主页：https://my.oschina.net/u/3375733
本篇文章同步在个人公众号：
