00-1010一份苦心解决，喜欢关注转发，一键三合一，让知识可以共享！
标题描述：
给定两个大小为m和n的正序(从小到大)阵列，nums1和nums2。请找出这两个正序数组的中值，并要求算法的时间复杂度为O(log(m ^ n))。您可以假设nums1和nums2都不是空的。
示例1:
S1=[1，3] nums2=[2]那么中位数是2.0。
示例2:
S1=[1，2] nums2=[3，4]那么中位数是(2 ^ 3)/2=2.5。
00-1010分析之前，我讲了一点。我真的没有想到O(log(m ^ n))的方法，只想到了O(m ^ n)的合并。没有想到怎么用二分法，看了解答才明白。但我自己明白。我会和你分享。
这个问题本身可能不难，但对于O(log(m ^ n))的时间复杂度来说可能就难了。
如果实在想不出好方法，先想想过关，应该用什么方法？
一种暴力的方法：你可以把两个数组加到一个总数组中，然后对数组进行排序。正常的顺序是O(nlogn)的时间复杂度。排序后，根据奇数和偶数取中位数。
方法2合并方法：给定的两个数组是有序的。想必熟悉合并排序的朋友应该能一下子想出这个方法，而且两个数组是有序的。只需按照以下过程完成合并：
要合并的两个数组分别设置了leftindex和rightindex两个指针，两个指针都是从0开始的。新数组还设置光标索引。比较两个数组的左索引和右索引位置的值。较小的一个被分配给新数组，新数组光标和较小的一个都增加1。
重复，直到遍历其中一个数组，另一个数组的剩余值可以直接加到后面。
实现代码：
public double find mediasentertedarrays(int[]nums 1，int[]nums 2){ 0
inta[]=new int[nums 1 . length nums 2 . length]；
intlindex=0，rindex=0；
int index=0；
while(lindexnums 1 . length rindexnums 2 . length){ 0
if(nums1[lindex]nums2[rindex])
{
a[index]=nums 1[lindex]；
}
else{
a[index]=nums 2[rindex]；
}
}
while(lindexnums 1 . length){ 0
a[index]=nums 1[lindex]；
}
while(rindexnums 2 . length){ 0
a[index]=nums 2[rindex]；
}
if(a.length%2==0)
return(double)(a[a . length/2-1]a[a . length/2])/2；
else{
返回[a . length/2]；
}
}二分法(O(log(m+n)))
想到有序的，又是O(log(m+n))的时间复杂度，估计大部分人都能想到二分，我当时也是一样，但是该怎么想呢这就是一个问题。记录下我当初错误的想法：
二分，二分找到两个中间的。然后正常有个长的，有个短的，根据两个数值比较分类推测中位数应该在哪个区间……然后大脑就断电了。
对于中位数的简单分析：
如果两个数组长度和为奇数，那么最终这个中位数是由一位数确定的。如果两个数组长度和为偶数，那么最终这个中位数是由两位数取平均值确定的。对两个数组的简单分析：
两个数组应该有一个长一点，另一个点一点(等长也不影响)。中位数可能让两个数组都分成两部分：一部分小于中位数，一部分大于中位数。但两个部分合起来总数量应该一致。对两数组合中位数位置分析：
我们知道两数组虽然可能等长(不影响)，但正常情况应该是一个长(m)一个短(n)。长短数组分别对应的坐标m1和n1和中位数坐标有什么关系？无论总和奇数偶数，都满足(m1+n1)=(m+n)/2;因为两个数组都是有序的所以总共小于中位数的占一半。其中m和n是定值。也就是不管你怎么变动，这两个坐标编号是总和为定值得！如何分析为定值得坐标
既然两个坐标的总和为定值，那么可不可以把其中一个当为自变量，一个看成自变量呢？比如x+y=5你不好分析但是y=5-x，你分析x同时y就确定了。对吧？那么选择长的那个作为变量还是短的那个作为变量呢？短的，为啥，主要因为如果从长的当成变量咱们有些区域无法对应到短的(因为长度即使加上短的所有也到不了一半，处理起来麻烦)：所以我们就用二分去查找小的这个区间，找到最终的结果，你可能会问：什么样情况能够满足确定这条线的附近就是产生中位数的？
二分进行查找编号的时候，满足左侧都比线右侧小才行。这种情况在二分查找就是一个平衡的结果。最后找到这个index线了。取值比较你还要有注意的地方：
取左侧的时候左侧如果有index为0，取右侧的时候index为最大值：总的来说：
根据短的进行二分查找位置，先找到线index，说明中位数在附近产生。（奇数偶数在查找因为要除2可以通用表达式）如果总个数奇数，那么就是线左侧最大的那个(两个比较或只有一个)如果总个数偶数，那么就是线左侧最大的那个(两个比较或只有一个)和线右侧最小的那个(两个比较或只有一个)的值取平均，注意是double类型。其他注意点，搞清index从0开始，搞清逻辑上的第几个和数组显示使用的第几个的index的区别。附上代码：
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) { if(nums1.length>nums2.length)//保证num1长度小，如果不小我交换一下 { int team[]=nums2.clone(); nums2=nums1; nums1=team; } int k=(nums1.length+nums2.length+1)/2;//理论中位数满足的位置 int left=0,right=nums1.length;//二分查找短的 while (left<right) {//找到对应位置 int m1=(left+right)/2;//在短的位置 int m2=k-m1;//在长的第几个 //System.out.println(m1+" "+m2); if(nums1[m1]<nums2[m2-1])//left右移 left=m1+1; else {//right左移 right=m1; } } //System.out.println(left+" "+k); //左侧最大和右侧最小那个先算出来再说，根据奇偶再使用 double leftbig= Math.max(left==0?Integer.MIN_VALUE:nums1[left-1], k-left==0?Integer.MIN_VALUE:nums2[k-left-1]); double rightsmall=Math.min(left==nums1.length?Integer.MAX_VALUE:nums1[left],k-left==nums2.length?Integer.MAX_VALUE:nums2[k-left]); //System.out.println(rightsmall); if((nums1.length+nums2.length)%2==0) { return (leftbig+rightsmall)/2; } else { return leftbig; } }结语
本次打卡结束，再接再励。
至于其他方法暂时先不学了，感觉这题还是挺有难度的，需要搞明白要点时候。
听说长得俊的更喜欢给人点赞收藏转发，一键三联，将知识分享给其他人，您的支持是我坚持的不断动力！
唯一原创公众号：bigsai,头条号：码农bigsai