求两个有序数组的中位数来源：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/题目给定两个有序数组nums1和大小为m和n的nums2。请求出这两个排序数组的中位数，算法的时间复杂度为O(log(m+n))。您可以假设nums1和nums2不会同时为空。示例1：nums1=[1,3]nums2=[2]则中位数为2.0示例2：nums1=[1,2]nums2=[3,4]则中位数为(2+3)/2=2.5解题思路使用方法：递归；这道题的数组是有序的，要求中位数，但是这道题可以转化为求第k小的数。如果是奇数，则第k位的数为中位数；如果是偶数，则取第k小数与第k+1小数之和的一半为中位数；因为数组是有序的，比较两个数组找第k小的数，不需要一个一个比较，一个一个消除。可以考虑对半排除，每次排除k/2个数。每次比较两个数组中的第k/2位（当k为奇数时，向下舍入），当其中一个数组的值较小时，表示该数组包含第k/2位和前一个数如果都小于第k位，则直接淘汰；此时k还需要减去被淘汰的位数，递归执行这一步；递归跳出的条件是其中一个数组为空，或者k为1；当k为1时，找此时第一个最小的数，只要两个数组的第一个数字较小的就是中位数；当数组为空且k不等于1时，此时，取第k小的非空数组的数。例子一：nums1:[1,3,5]nums2:[1,2,3,4,5,6,7,8]在这个例子中，假设需要第6个最小的数字。比较第3个数字k/2。nums1的第3个数是5，nums2的第3个数是3,5>3，所以去掉下面数组中的3个数，比较[1,3,5]和[4,5,6,7,8]，此时淘汰了3个数，所以k需要减3，此时k=3。继续比较；k/2不可整除，向下舍入为1，比较两个数组的第一个数，此时1<4，去掉第一个数组中的1，留下[3,5]和[4,5,6,7,8],k为3-1=2,再比较;k/2为1,3<4，去掉第一个数组中的3，剩下[5]和[4,5,6,7,8]，k为2-1=1。此时k=1，也就是找第一个最小的数。此时比较剩余两个数组的首位，去掉较小的数，也就是第一个最小的数，即4。例2：考虑数组长度小于k/2的情况：nums1:[1,2]nums2:[1,2,3,4,5,6,7,8,9,10]还要找到第6个最小的数字。解题思路和例1一样，先比较第k/2位的大小，k/2=3。由于第一个数组的长度小于3，此时直接取最后一个数2，在第二个数组中取第三个数，即3，其中2<3，而第2个数第一个数组直接去掉，k变成6-2=4。由于此时第一个数组为空，此时直接取另一个数组的第k小数，即第4位小数，即4，即原来要求的两个数组中第6小的数.因为每次循环都会减少k/2个元素，所以时间复杂度为O(log(k))，而这道题中的k为(m+n)/2，所以最终复杂度为O(log(m+n))。代码实现类Solution:deffindMedianSortedArrays(self,nums1,nums2)->float:m=len(nums1)n=len(nums2)#这里默认是偶数，如果是奇数，计算两次相同的k值med_left=(m+n+1)//2med_right=(m+n+2)//2return(get_k_num(nums1,0,m-1,nums2,0,n-1,med_left)+get_k_num(nums1,0,m-1,nums2,0,n-1,med_right))/2defget_k_num(nums1,head1,end1,nums2,head2,end2,k):len1=end1-head1+1len2=end2-head2+1#递归跳出条件if(len1==0):returnnums2[head2+k-1]if(len2==0):returnnums1[head1+k-1]if(k==1):returnmin(nums1[head1],nums2[head2])i=head1+min(len1,k//2)-1j=head2+min(len2,k//2)-1if(nums1[i]>nums2[j]):返回get_k_num(nums1,head1,end1,nums2,j+1,end2,k-(j-head2+1))否则：返回get_k_num(nums1,i+1,end1,nums2,head2,end2,k-(i-head1+1))实现效果以上就是本文的主要内容：我把这篇文章的解题思路记下来了，当我回过头来看，发现纯文字感觉逻辑上会有点乱，下次会尝试用图例来完善这部分的内容。欢迎关注微信公众号《书所集录》
