上一篇:3.无重复字符的最长子串(LongestSubstringWithoutRepeatingCharacters)
题目(Hard)
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
有两个大小为 m 和 n 的排序数组 nums1 和 nums2 。
请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。
脑洞时间
看到题目的第一时间，思路不是很清晰，后面看到算法时间复杂度的要求就更是有点迷茫了。思考中......
回过头来，看到题目所说的是两个有序数组。如果不考虑时间复杂度的问题，还是挺好解决的。
最简单粗暴的就是通过遍历合并两个数组形成一个新的有序数组，这样中位数就显而易见了。这里暂且不讨论这种最容易想到的方法。
关键信息：有序！！！针对两个有序数组，大小分别为m和n，我们只需要从低往高依次数(n+m)/2个元素即可：
对于一个长度为n的已排序数列a，若n为奇数，中位数为a[n / 2 + 1] ,
若n为偶数，则中位数(a[n / 2] + a[n / 2 + 1]) / 2
如果我们可以在两个数列中求出第K小的元素，便可以解决该问题
不妨设数列A元素个数为n，数列B元素个数为m，各自升序排序，求第k小元素
取A[k / 2] B[k / 2] 比较，
如果 A[k / 2] > B[k / 2] 那么，所求的元素必然不在B的前k / 2个元素中(证明反证法)
反之，必然不在A的前k / 2个元素中，于是我们可以将A或B数列的前k / 2元素删去，求剩下两个数列的
k - k / 2小元素，于是得到了数据规模变小的同类问题，递归解决
如果 k / 2 大于某数列个数，所求元素必然不在另一数列的前k / 2个元素中，同上操作就好。
假设我们要取第k个元素的时候，在数组a中间选择的元素点是i，这个i表示的是a中间的第i个，不是索引i。那么，对应的在另外一个数组b中间对应位置的k-i个是我们需要比较的对象。
如果这个时候位置为i的元素，也就是数组a里a[i - 1]的元素等于对应比较的元素，即b[k - i - 1]的元素，这表示包含这两个元素在内以及它们之前的数组a,b中的所有元素正好有k个。我们取a[i-1]或者b[k-i-1]作为找到的目标结果值。当然这个时候a[i-1] == b[k-i-1]。
假如a[i - 1] > b[k - i]，这个时候表示a串中第i个元素它在对应的数组b中排到比期望的还要靠后才满足a[i-1] < b[m], m > k - i。所以这个时候我们要找的元素肯定在a[i - 1]的左边范围内。反之亦然。
废话少说撸代码
# 穷举遍历法 时间复杂度O(N),虽然也可以实现功能，但是不符合O(log (m+n))的要求
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
l = len(nums1) + len(nums2)
print(l)
if l % 2 == 0:
return (self.findMedian(nums1, nums2, int(l/2))+self.findMedian(nums1, nums2, int(l/2)+1))/2.0
else:
return self.findMedian(nums1, nums2, int(l/2)+1)
def findMedian(self, nums1, nums2, l):
p = 0
q = 0
for i in range(0, l-1):
if p >= len(nums1) and q < len(nums2):
q = q + 1
elif p < len(nums1) and q >= len(nums2):
p = p + 1
elif nums1[p] > nums2[q]:
q = q + 1
else:
p = p + 1
if p >= len(nums1):
return nums2[q]
elif q >= len(nums2):
return nums1[p]
else:
return nums1[p] if nums1[p] < nums2[q] else nums2[q]
问题解决了吗
如果直接在leetCode提交这段代码，你会发现不符合题意要求。因为题目要求的时间复杂度是O(log (m+n))，而我们的只能达到O((m+n)/2)。
思考良久，我还真没想到别的方式。。。
他山之石
思考良久也做不出来啊，根据这个时间复杂度的要求…应该不能用循环遍历，可能是递归和二分法结合。可惜我是个小白做不出来。
然后去百度，果然答案真真是骨骼惊奇！
首先在随机位置将A分成两部分：
left_A | right_A
A [0]，A [1]，...，A [i-1] | A [i]，A [i + 1]，...，A [m-1]
由于A有m个元素，所以有m + 1种切割（i = 0〜m）。其中：left_A.size() = i，right_A.size() = m-i。注意：当i = 0时，left_A为空，当i = m时，right_A为空。
同样，在随机位置将B切成两部分：
left_B | right_B
B [0]，B [1]，...，B [j-1] | B [j]，B [j + 1]，...，B [n-1]
将left_A和left_B放入一个集合，并将right_A和right_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]
如果我们可以确保：
1）left_part.size() == right_part.size()
2）max（left_part）<= min（right_part）
那么我们将{A，B}中的所有元素划分为两个长度相等的部分，一个部分总是大于另一个部分。然后中值=（max（left_part）+ min（right_part））/ 2。
为了确保这两个条件，只需要确保：
（1）i + j == m-i + n-j（或：m-i + n-j + 1）
如果n> = m，我们只需要设置：i = 0〜m，j =（m + n + 1）/ 2-i
（2）B [j-1] <= A [i]，A [i-1] <= B [j]
为什么一定要n> = m？因为必须确保j是合法索引，因为0 <= i <= m和j =（m + n + 1）/ 2-i。如果n <m，则j可以是负数，这将导致错误的结果。
在[0，m]中搜索i，找到一个切分点i（j =（m + n + 1）/ 2-i）：
使得B [j-1] <= A [i]和A [i-1] <= B[j]。
我们可以按照以下步骤进行搜索：
<1>设置imin = 0，imax = m，然后开始搜索[imin，imax]
<2>设置i =（imin + imax）/ 2，j =（m + n + 1）/ 2-i
<3>现在left_part.size() == right_part.size()。而且只有3种情况：
(1) B[j-1] <= A [i]和A [i-1] <= B [j]
意味着找到了切分点i，停止搜索。
(2) B[j-1]> A [i]
意味着A [i]太小。必须调整i得到B [j-1] <= A [i]。而i只能增加不能减小，因为当i减小时j将增加，因此，B [j-1]增加并且A [i]减小，永远不会满足。所以必须增加i。也就是说，调整搜索范围为[i + 1，imax]。因此，imin = i + 1和然后回到第<2>步。
(3) A [i-1]> B [j]
意味着A [i-1]太大，必须减少i得到A [i-1] <= B [j]。因此，设置imax = i-1然后回到第<2>步。
当找到切分点i时，中值为：
max（A [i-1]，B [j-1]）（当m + n是奇数时）
或（max（A [i-1]，B [j-1]）+ min（A [i]，B [j]））/ 2（当m + n为偶数时）
注:以上分析来自简书作者：yzawyx0220
废话少说再撸代码
def findMedianSortedArrays(self, nums1, nums2):
# 有一个数组为空
if len(nums1) == 0 and len(nums2) > 0:
return nums2[int(len(nums2)/2)] if len(nums2) % 2 == 1 else (nums2[int(len(nums2)/2)-1]+nums2[int(len(nums2)/2)])/2.0
if len(nums2) == 0 and len(nums1) > 0:
return nums1[int(len(nums1)/2)] if len(nums1) % 2 == 1 else (nums1[int(len(nums1)/2)-1]+nums1[int(len(nums1)/2)])/2.0
# 保证n > m
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
imin, imax = 0, m
'''
用i,j分别将两个数组随机分成两部分(这里取中间)，nums1长度m,nums2为n
分别为nums1_left,nums1_right,nums2_left,nums2_right
我们再将nums1_left,nums2_left归为nums_left
将nums1_right,nums2_right归为nums_right
只要我们确保：
1.len(nums_left) = len(nums_right)
2.max(nums_left) <= min(nums_left)
那么中值就为:(max(nums_left)+min(nums_left))/2
为了满足条件1，需使得i+j = m-i+n-j+ 则 j = (m+n+1)/2
为了满足条件2，需使得：
nums1[i-1] <= nums2[j]
nums2[j-1] <= nums1[i]
所以，我们只要找到满足条件的i的位置即可
'''
while imin <= imax:
i = int((imin+imax)/2)
j = int((m+n+1)/2) - i
# i太小增加i
if i < m and j > 0 and nums1[i] < nums2[j-1]:
imin = i + 1
# i太大减少i
elif i > 0 and j < n and nums1[i-1] > nums2[j]:
imax = i-1
else:
# i或j为边界值
if (i == 0):
max_left = nums2[j-1]
elif (j == 0):
max_left = nums1[i-1]
else:
max_left = nums1[i-1] if nums1[i-1] > nums2[j-1] else nums2[j-1]
break
# 数组大小和奇数
if (m+n) % 2 == 1:
return max_left
if i == m:
min_right = nums2[j]
elif j == n:
min_right = nums1[i]
else:
min_right = nums1[i] if nums1[i] < nums2[j] else nums2[j]
return (max_left+min_right)/2.0
->
->
->
->
下一篇:5. 最长回文子串(LongestPalindromicSubstring)
->
->
->
------------------------------20180315夜 初稿
------------------------------20180316夜 再稿
刷Leetcode，
在我看来，
其实是为了维持一种编程状态！
