也是看了一篇很好的博客，思路很清晰，只是有些地方感觉博主没有详细解释，后来理解了，做了一个小总结。原博客链接：点击打开链接
题目还是昨天的那道题目：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1[1,3]
nums2[2]
中位数：2.0
示例 2:
nums1[1,2]
nums2[2,3]
中位数:(2+2)/2=2.0
其中要求算法时间复杂度，也可以利用分治法来解决。此时的分治法，需要将两个有序数组合并看作一个新的数组。然后进行分割。
思路总结（具体思路原创博主更为详细，可以参照）：
1、因为是两个有序数组，所以需要两个割点C1，C2。若将两个数组(都是升序排序的数组)分别在一个割点处分为两半，那么L1（数组前半部分的最右边的元素)一定是小于R1(数组后半部分最左边的元素)，同理L2<R2。 因为要找两个有序数组的中位数（为了方便奇偶性的区分，我们将两个数组分别虚拟设置为奇数，所以两个数组看为一个数组的时候，元素个数为偶数，中位数=(m1+m2)/2，此时只要找到m1,m2中位数便可以求出），若割点刚好处于中间，此时只需要找到当L1<R2,L2<R1的时候（两个数组前半部分都保证了比后半部分小的时候），比较L1和L2的数值，找选出最大的（因为左半部分从左到右是依次增大，那么找出最靠近右边的那个数m1）。同理当R1>L2,R2>L1时候，比较R1和R2的数值，找出最小的（因为右半部分从左到右依次增大，那么找出最靠近左边的那个数m2）。此时(m1+m2)/2便是要求的中位数。
2、首先一个数组要求中位数，必须是排序好，而且要分奇偶，才能求出中位数。现在是两个数组，奇偶性都在不确定，所以原博主很明智地将数组进行了处理，通过虚拟地加入#符号，使得数组恒为奇。（例如：1，2，48，90 虚拟加#符号后变为：#1#2#48#90#），此处的处理是通过公示：2n+1始终是奇数而来的。代码中并没有实际加入符号#，只是将数组的长度进行了2n+1的翻倍。
3、所以只要找到处于中间的那个割点K，并找到K左右的两个数值，就可以求出中位数。对于单个有序数组，K的位置就是在数组长度一半的位置（当然要分奇偶）。偶数的话就是K左右的两个数值相加除以2，奇数的话，也就是K所在的位置。那么对于两个有序数组的话，如果left1,left2(两个数组的左半部分)的元素个数相加等于K的时候，比较L1，L2找出最大的那个数值，那个数值就是K左边的值，同理，K右边的值就是R1，R2中最小的那个。若假设数组1的割点为C1，数组2的隔点为C2，那么当C1+C2 = K的时候，就可以进行比较。
4、比较的时候，如果L1 > R2的时候，就需要将C1往左移动（左边数值更小），将C2往右移动（右边数值更大），直到满足L1<R2.同理，如果L2 > R1的时候，就需要将C2往左移动，C1往右边移动，直到满足L2<R1。此处需要考虑越界的问题，若当C1=0，移动到了最左边或者C2移动到了最右边，都还不满足L1 < R2的时候，说明数组1 > 数组2，此时中位数在数组2中，若当C2=0，移动到了最左边或者C1移动到了最右边，还不满足L2<R1的时候，说明数组1 < 数组2，此时中位数在数组1中。
5、假设数组1长度为n,数组2长度为m,并且n<m(从最小长度进行二分)。将数组长度进行虚处理，然后再把两个数组看作是数组A。此时长度为（2m+1)+(2n+1)=2m+2n+2 此时从最中间隔开，k = (2m+2n+2)/2=(m+n+1),因为数组A是从下标0开始计数的，所以在程序中K实际等于(m+n).知道K值之后，C1，C2任意知道其中一个，便可以确定另外一个，此处对长度较小的数组进行二分，所以确定C1后再确定C2， C2 = k-C1=m+n-C1.此时我们将数组进行了虚拟的加#，所以要确定原来数组元素的真正位置，就包含一个映射关系。L1 =(C1-1)/2 L2=(C2-1)/2 R1=(C1/2) R2=(C2/2)
代码实现：
#include<iostream>
#include<vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int n = nums1.size();
int m = nums2.size();
if(n > m) //保证对数组长度最短的进行二分
return findMedianSortedArrays(nums2,nums1);
int L1,L2,R1,R2,c1,c2,left = 0, right = 2*n; //虚拟加#符号之后，数组长度为2n+1,但是数组下标从0开始，所以要减去1
while(left <= right)//二分法框架
{
c1 = (left + right) / 2; //c1是二分的结果
c2 = m + n - c1;//k = m+n 确保两个数组左半部分加起来等于k
L1 = (c1 == 0)?INT_MIN:nums1[(c1-1)/2]; //根据映射关系还原数组元素的原下标
R1 = (c1 == 2*n)?INT_MAX:nums1[c1/2];
L2 = (c2 == 0)?INT_MIN:nums2[(c2-1)/2];
R2 = (c2 == 2*m)?INT_MAX:nums2[c2/2];
if(L1 > R2)
{
left = c1-1;
}
else if(L2 > R1)
{
right = c1+1;
}
else
{
break;
}
}
return (double)(max(L1,L2)+ min(R1,R2))/2;
}
int main()
{
vector<int>nums1(4);
vector<int>nums2(3);
for(int i=0; i<4;i++)
{
cin >> nums1[i];
}
for(int i=0; i<3; i++)
{
cin >> nums2[i];
}
cout<< findMedianSortedArrays(nums1,nums2)<< endl;
return 0;
}
我也是一个搬运工，做了一个总结，详细的知识点可以参照原博客 点击打开链接
感觉原创很厉害的样子！！