题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/
参考文献：
思路：
实在是脑子转不过来，看了一下解法，然后就把自己的理解讲一下吧。
有两个规律需要说下：
1.在某个数列头尾删去相同数量的元素，其中位数是不变的。比如[1,2,3,4]删去1和4.
2.如果两个数列的中位数是m1, m2，那么合并后的数列的中位数的值肯定在[m1,m2]范围内。
既然题目是要Log级别的复杂度，就要想到要用折半法把问题的规模降低…举个例子，假设有[1,2,4,6,6,8]和[1,5,7,8,10,25,36]两个数列，很容易算出他们的（前序 ）中位数分别是4和8，而他们合并后的中位数的值在[4,8]之间。
然后可以删去无用的值，[1,2]与[10,25,36]. 但由于规律1的限制，如果后面删了3个的话，合并后删减的数列会发生变化（本例中奇偶性都变了），我们只能删去min(2,3)=2个元素…这种删值从理论上讲就是折半了，然后搞一波递归就行了。
最最最基本的思路如下：
两个有序数列Ary1, Ary2（假设升序排列）的中位数分别为m1,m2
if m1 == m2:
LUCKY!!!
elif m1 < m2:
取（Ary1的后半段，Ary2的前半段）再算
else
取（Ary1的前半段，Ary2的后半段）再算
由于题设里面俩数组是不等长的，所以里对其中某个数组n<=2时处理方法需要注意…
代码：
int max(int x, int y) {
return x>y ? x : y;
}
int min(int x, int y) {
return x<y ? x : y;
}
double getMedian(int* nums, int size) {
if (size == 0)
return -1;
if (size % 2 == 0) {
//Even number
return (nums[size / 2] + nums[size / 2 - 1]) / 2.0;
}
else {
return nums[(size - 1) / 2];
}
}
double findMedianMerge(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int count = 0;
int n1Count = 0;
int totalSize = nums1Size + nums2Size;
int t1, t2;
if (totalSize % 2 == 0) {
t1 = totalSize / 2;
t2 = t1 + 1;
}
else {
t1 = -1;
t2 = totalSize / 2 + 1;
}
double sum = 0;
int curVal;
while (n1Count < nums1Size) {
if (*nums1 < *nums2) {
n1Count++;
curVal = *nums1;
nums1++;
}
else {
curVal = *nums2;
nums2++;
}
count++;
if (count == t1 || count == t2) {
sum += curVal;
}
else if (count >= t2) {
break;
}
}
if (count < t1) {
//Not finished
nums2 += (t1 - count - 1);
count = t1;
sum += *nums2;
nums2++;
}
if (count < t2) {
nums2 += (t2 - count - 1);
sum += *nums2;
}
if (t1 == -1)
return sum;
else
return sum / 2.0;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int totalSize = nums1Size + nums2Size;
if (nums1Size > nums2Size) {
//Keep ary1 shorter than ary2
int* temp = nums1;
int t = nums1Size;
nums1 = nums2;
nums1Size = nums2Size;
nums2 = temp;
nums2Size = t;
}
if (nums1Size == 0) {
return getMedian(nums2, nums2Size);
} else if (nums1Size == 1) {
if (nums2Size == 1) {
return (nums1[0] + nums2[0]) / 2.0;
}
else {
return findMedianMerge(nums1, nums1Size, nums2, nums2Size);
}
}
else if (nums1Size == 2) {
if (nums2Size == 2) {
return (max(nums1[0], nums2[0]) + min(nums1[1], nums2[1])) / 2.0;
}
else {
return findMedianMerge(nums1, nums1Size, nums2, nums2Size);
}
}
//Slice
double m1 = getMedian(nums1, nums1Size);
double m2 = getMedian(nums2, nums2Size);
if (m1 == m2) {
//Got lucky
return m1;
}
else if (m1 < m2) {
//Slice L-nums1 and R-nums2
int cut = (nums1Size - 1) / 2;
return findMedianSortedArrays(nums1 + cut, nums1Size - cut, nums2, nums2Size - cut);
}
else {
//Slice R-nums1 and L-nums2
int cut = (nums1Size - 1) / 2;
return findMedianSortedArrays(nums1, nums1Size - cut, nums2 + cut, nums2Size - cut);
}
}