Description：
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)).
思路：找出两个已经排好序数组的中位数。可以使用合并排序中的merge，然后直接找出中位数就能AC。时间复杂度为O(m+n)。但是！！这毕竟是一个Hard的题！时间复杂度要求O(log(m+n))!
先上merge代码：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = 0, n = 0;
if(nums1 != null) {
m = nums1.length;
}
if(nums2 != null) {
n = nums2.length;
}
int[] res = new int[m + n];
//merge
int cur = 0, i = 0, j = 0;
while(i<m && j<n) {
if(nums1[i] < nums2[j]) {
res[cur] = nums1[i];
i ++;
}
else {
res[cur] = nums2[j];
j ++;
}
cur ++;
}
while(i < m) {
res[cur] = nums1[i];
i ++;
}
cur ++;
while(j < n) {
res[cur] = nums2[j];
j ++;
cur ++;
}
//findMedian
int length = m + n;
double ans = 0.0;
//
if((length & 1) != 0) {
ans = res[length / 2];
}
else {
ans = (double)(res[length/2 - 1] + res[length/2]) / 2.0;
}
return ans;
}
}
严重怀疑Java的测试数据和C/C++的不一样。要不效率会这么高！
O(log(m+n))的二分代码网上都是一样的，就不贴了。
http://blog.csdn.net/zxzxy1988/article/details/8587244