给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1 | nums1 = [1, 3] |
示例 2:
1 | nums1 = [1, 2] |
简单解析:最重要的就是求两个有序数组中的第k大,有几个小细节注意一下就行了。
如,求两个有序数组$A$和$B$的第$K$大的数,那么将$A$和$B$的前$\frac{K}{2}$的数组分别切割出来,比较$A[\frac{K}{2}]$和$B[\frac{K}{2}]$的大小就可以消去$\frac{K}{2}$个数,为什么那?因为如果$A[\frac{K}{2}]<B[\frac{K}{2}]$,那么$A[0:\frac{K}{2}]$肯定都小于$B[\frac{K}{2}]$(废话),所以接下来只需要在剩下的数中找第$\frac{K}{2}$大的数就行了(一些细节没描述),详见代码。
时间复杂度:$O(log_{2}{(len(A)+len(B)}))$
1 | class Solution { |