每日算法（5）求数组中位数

我就是我 2022-03-09 04:35 252阅读 0赞

> 给定两个大小为 m 和 n 的有序数组 nums1 和 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

根据中位数的定义：在一组数中有一半的元素比这个数小，或者一半的元素比这个数大，则这个数就是中位数

注意：这道题的不难，可是对算法的时间复杂度有一定要求，所以这道题的难点在于对时间复杂度的掌握程度。其次有序数组的意思数组中的元素是有顺序的要不就是由大到小，要不就是由小到大。  
(1)找出意味着这是一个查找算法题  
(2)算法复杂度log级别，就是提示你是二分查找  
二分查找实现一般为递归  
（1）递归包括递归体  
（2）终止条件  
1、排序法：  
看到这个首先想到的就是把两个数组合起来，放在一起，然后排序求中位数：

def getMiddle(a,b):
        a.extend(b)
        c = sorted(a)
        print(c)
        lenc=len(c)
        if lenc%2==1:
            return c[lenc//2]
        else:
            return (c[lenc//2-1]+c[lenc//2])/2

由于python中内置的排序算法的时间复杂度为o(n\*log(n))，所以不符合题意  
原文：https://blog.csdn.net/xushikou1514/article/details/84938060  
2、递归法（官方思路）  
首先，让我们在任一位置 i 将 A 划分成两个部分：  
![在这里插入图片描述][20190312124941790.png]  
采用同样的方式，我们在任一位置 j将 B 划分成两个部分：  
![在这里插入图片描述][20190312125030395.png]

![在这里插入图片描述][20190312125450859.png]如果满足以下条件：  
![在这里插入图片描述][2019031212511619.png]  
那么这组数的中位数就为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]

"""
 解题思路：初看这题可以理解为，把两个数组合并后排序，再找到(m+n)/2的数即中位数 
 而有个要求是时间复杂度是log(m+n),我们知道所有排序算法时间复杂最低也只能是nlogn，所以用排序来解决是不行的 
 既然题目是要求找中位数，我们可以从中位数的概念入手，中位数是指在数组中有一半数比它小，一半数比它大 
 由于这两个数组都是有序数组，我们假设为A数组和B数组，如果我们从下标为i的地方把A数组分为两半，左边的数肯定比A[i]小，右边比A[i]大 
 同理把B数组从下标为j的地方分为两半 
 left_part | right_part 
 A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1] 
 B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1] 
 那只要满足两个条件，我们就可以顺利找到中位数 
 1.len(left_part)==len(right_part) 相当于 i+j=m-i+n-j 
 2.min(right_part)>=max(left_part) 相当于 B[j]>=A[i-1] && A[i]>=B[j-1] 
 对于第一个条件: 
 我们可以推出j=(m+n)/2 - i,也就是i的值确定了，j的值就确定了，也就是说我们只要把i的值确定下来满足第二个条件就行 
 对于第二个条件： 
 我们需要满足 B[j]>=A[i-1] && A[i]>=B[j-1]，不满足的条件有两种： 
 一是B[j] < A[i-1],说明i的值太大了，你想想A[i]的值肯定大于A[i-1]，如果i继续加大，条件永远无法满足，所以只能减小i 
 二是A[i] < B[j-1],说明i的值太小了，需要加大i的值 
 明白了这些，我们只需要根据条件去增加或缩小i的值就可以了，由于是有序数组，我们可以用二分法变化i的值 
 最后我们再看看满足条件B[j]>=A[i-1] && A[i]>=B[j-1]时怎么得到中位数 
 max(left_part)=max(A[i-1],B[j-1]); 
 min(right_part)=min(A[i],B[j]); 
 如果数组之和是偶数，中位数=(max(left_part)+min(right_part))/2 
 如果数组之和是奇数，中位数=max(left_part)或者min(right_part)，那取哪个呢，哪边多一个就取哪边 
 我们可以将j=(m+n)/2 - i改为j=(m+n+1)/2 - i来保证j的值大些，从而保证len(left_part)>left(right_part) 
 也可以将j=(m+n)/2 - i改为j=(m+n-1)/2 - i来保证j的值小些, 从而保证len(right_part)>left(left_part) 
 最后就是一些特殊情况了： 
 首先由于j是由i决定的，j=(m+n)/2 - i, i的取值范围是0到m,也就是说j可能的值是(n-m)/2 到(m+n)/2，由于j不能为负，那么反推n>=m 
 如果i==0或者i==m时，A数组有一边是没有值的，得特殊处理 
 同理j==0或者j==m时，B数组有一边也是没有值的，得特殊处理 
 """
 
 class Solution:
 def findMedianSortedArrays(self, nums1 , nums2):
 m = len(nums1)
 n = len(nums2)
 #始终保证n比m大
 if m>n:
 m,n,nums1,nums2 = n,m,nums2,nums1
 imax = m
 imin = 0
 half_ls = int((m+n+1)/2)
 while imin<=imax:#开始循环，循环的终止条件是整个数组搜索完毕
 i = int((imax+imin)/2) #int是向下取整如 2.5就为2
 j = half_ls - i #i变化，j也变化，但是始终左边等于右边
 if i < m and nums1[i]<nums2[j-1]:
 #第一个if，要考虑的是这样的一个例外：[0],[1, 3]
 imin = i + 1
 elif i > 0 and nums1[i-1]>nums2[j]:
 #第二个if，考虑的例外是这样：[2],[1]
 imax = i - 1
 else:##最好的情况即nums1[i-1]<nums2[j]，nums2[j-1]<nums1[i]
 if i == 0:#nums1为空数组
 max_left = nums2[j-1]
 elif j == 0:#nums2为空数组
 max_left = nums1[i-1]
 else:
 max_left = max(nums1[i-1],nums2[j-1])
 if i == m: #nums1为空
 min_right = nums2[j]
 elif j == n: #nums2为空
 min_right = nums1[i]
 else:#nums1和nums2同时不为空
 min_right = min(nums1[i],nums2[j])
 if (m+n)%2==1:
 return max_left
 if (m+n)%2==0:
 return (max_left+min_right)/2.0

[20190312124941790.png]: /images/20220309/42eb1dc8d5b6463a975d18860d0c1969.png
[20190312125030395.png]: /images/20220309/c40f3b40ad6246b7ba8ca4bf249b561e.png
[20190312125450859.png]: /images/20220309/52ac8d472756483db4099175786de34b.png
[2019031212511619.png]: /images/20220309/f956cae0a8a949d5b00f40c7f3ae4699.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20220309/265069fdcc8446a8b61c8cb74e27df20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20220309/31357df856784e55950a94d56099acd5.png