題目要求
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
??題目翻譯：給定兩個有序數(shù)組nums1和sums2睁本，長度分別是m和n，求出兩個數(shù)組的中間值忠怖，要求算法的復雜度是O(log(m+n))呢堰。
題目分析
該問題可以抽象為一個數(shù)學問題：求第K小的值(或者第K大的值)。假若先合并兩個數(shù)組凡泣，復雜度是O(m+n)枉疼，不符合要求。題目的復雜度要求O(log (m+n))給了我們提示：可以用二分查找來提高查找效率鞋拟。算法設計采用遞歸二分查找骂维，每一次遞歸截斷一半的查找空間。
函數(shù)的偽碼如下findk(int[] a, int m, int[] b, int n, int k)
- 假如數(shù)組a長度大于數(shù)組b严卖，交換兩個數(shù)組席舍，保證任何時候，數(shù)組a的長度小于等于數(shù)組b哮笆，簡化條件判斷
- 當數(shù)組a空，則返回數(shù)組b的第k個值汰扭，數(shù)組索引是k-1
- 當返回第一個最小值的時候(k=1)稠肘，返回數(shù)組a和數(shù)組b最小值中較小的一個
- 截斷：pa = Math.min(k/2, m)；pb = k - pa萝毛； 可得pa+pb = k项阴，如果a[pa-1] < b[pb-1]，顯然可證：a[pa-1]一定小于第k個值，又因為數(shù)組a有序环揽，因此數(shù)組的第0到第pa-1個元素均小于第K個值略荡，可以截斷，同時k = k-pa歉胶，縮小一半的查找空間汛兜。同理可證，a[pa-1] > b[pb-1]時通今，可截斷b[0……pb-1]部分粥谬，k = k-pb
代碼-Java實現(xiàn)
import java.util.*;
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
/**
* 假設兩個數(shù)組長度之和是奇數(shù)，則中間數(shù)是第 total/2+1 個數(shù)
* 假設兩個數(shù)組長度之和是奇數(shù)辫塌，則中間數(shù)是第 total/2 個數(shù) 和 第 total/2+1 個數(shù)的平均值
*/
if (total%2 == 1) {
return findk(nums1, nums1.length, nums2, nums2.length, total/2+1);
} else {
// 為什么傳進去的數(shù)組不會被修改漏策？原因是findk中調(diào)用的是java.util.Arrays.copyOf()實現(xiàn)深拷貝
// ToDO 偶數(shù)情況的尋找第 total/2+1 個數(shù)字可以在 total/2 上再做一次查找就可以，怎么實現(xiàn)這個優(yōu)化臼氨？
return (findk(nums1, nums1.length, nums2, nums2.length, total/2) +
findk(nums1, nums1.length, nums2, nums2.length, total/2+1)) / 2.0;
}
}
// 遞歸查找第K個值
public double findk(int[] a, int m, int[] b, int n, int k) {
/**
* 處理該問題中出現(xiàn)的遞歸的3個邊界條件
*/
// 保證任何時候掺喻，數(shù)組a的長度小于等于數(shù)組b，簡化條件判斷
if (m>n)
return findk(b, n, a, m, k);
// 當數(shù)組a空储矩，則返回數(shù)組b的第K個值感耙，數(shù)組索引是k-1
if (m==0)
return b[k-1];
// 當返回第一個最小值的時候(k=1),返回數(shù)組a和數(shù)組b最小值中較小的一個
if (k==1)
return Math.min(a[0], b[0]);
/**
* pa+pb = k,如果a[pa-1] < b[pb-1],顯然可證：a[pa-1]一定小于第k個值,
* 又因為數(shù)組a有序，因此數(shù)組的第0到第pa-1個元素均小于第K個值椰苟，可以截斷抑月，
* 同時k = k-pa, 縮小一半的查找空間。
*
* 同理可證舆蝴，a[pa-1] > b[pb-1] 時谦絮，可截斷b[0……pb-1]部分，k = k-pb洁仗。
*/
int pa = 0, pb = 0;
pa = Math.min(k/2, m); pb = k - pa;
if (a[pa-1] < b[pb-1]){
// java.util.Arrays.copyOf()實現(xiàn)深拷貝层皱，內(nèi)部實現(xiàn)是調(diào)用System.arraycopy
a = Arrays.copyOfRange(a, pa, m);
return findk(a, m-pa, b, n, k-pa);
} else if (a[pa-1] > b[pb-1]) {
// 同上一條注釋
b = Arrays.copyOfRange(b, pb, n);
return findk(a, m, b, n-pb, k-pb);
} else {
return a[pa-1];
}
}
// 測試模塊
public static void main(String[] args) {
Solution solution = new Solution();
int[] sum1 = {3,4};
int[] sum2 = {1,2};
double result = solution.findMedianSortedArrays(sum1, sum2);
System.out.println(result);
}
}
