给定两个大小为 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
拿到题之后，我以为是两个数组，分别取中位数然后相加除二就好了...
好吧，我以后看题要仔细一点了...
没什么可以说的，先来wawawa三连发，真爽
然后，我就把这两个放进一个数字然后判断奇偶性输出就OK了
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
lenth1 = len(nums1)
lenth2 = len(nums2)
lenth = lenth1 + lenth2
i, j = 0, 0
p1, p2 = 0, 0
nums = [0] * (lenth)
if lenth1 == 0 and lenth2 == 0:
return
elif lenth1 == 0:
nums = nums2
elif lenth2 == 0:
nums = nums1
else:
for index in range(lenth):
if nums1[i] <= nums2[j] and p1 == 0:
nums[index] = nums1[i]
if i != lenth1-1:
i += 1
else:
p1 = 1
elif nums1[i] <= nums2[j] and p1 == 1:
nums[index] = nums2[j]
if j != lenth2-1:
j += 1
elif nums1[i] > nums2[j] and p2 == 0:
nums[index] = nums2[j]
if j != lenth2 -1:
j += 1
else:
p2 = 1
else:
nums[index] = nums1[i]
if i != lenth1-1:
i += 1
# print(nums)
if lenth%2 == 1:
return nums[int(lenth/2)]
else:
return (nums[int(lenth/2)] + nums[int(lenth/2)-1])/2
nums1 = []
nums2 = []
sol = Solution()
print(sol.findMedianSortedArrays(nums1, nums2))好了，成功通过，结束了，nice!
睡了睡了，晚安
！！！！
不对啊，这道题不是困难的么，我后来去看了看题解，EMMM...
果然用到了二分查找的方法，觉得挺有意思的，把两个数组分成了4部分来查找，在这里ma一下
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
首先，让我们在任一位置 i，将 A 划分成两个部分：
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]我们能够得到
? left_A | right_A
? A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
对于B也是当然
将两个放在一起更加明显了，就有思路啦！
把新的集合分别命名为left_part 和right_part：
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]median = (left_part+right_part)/2
我们能够得出的条件：
i+j=n+m-i-j(假设这几个部分长度相同，设n>=m使j不为负数)
B[j-1]<A[i] and B[j]>A[i-1]
然后就是简单的二分查找的步骤了，这里就不多说了，直接上代码了
class Solution:
def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
m, n = len(A), len(B)
if m == 0 and n == 0:
return
if n == 0:
if m%2 == 1:
return A[int(m/2)]
else:
return (A[int(m/2)]+A[int(m/2)-1])/2
if m == 0:
if n%2 == 1:
return B[int(n/2)]
else:
return (B[int(n/2)]+B[int(n/2)-1])/2
if m > n:
A, B, m, n = B, A, n, m
imin, imax, half_len = 0, m, int((m + n + 1) / 2)
while imin <= imax:
i = int((imin + imax) / 2)
j = half_len - i
if i < m and B[j-1] > A[i]:
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
imax = i - 1
else:
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0
A = []
B = []
sol = Solution()
print(sol.findMedianSortedArrays(A,B))额，连接放在下面，有兴趣的可以直接去了解，试一试
链接：https://leetcode-cn.com/problems/two-sum/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/
来源：力扣（LeetCode）
今天是第一天，以后继续保持！
原文：https://www.cnblogs.com/fanwenkeer/p/11253007.html