4. Median of Two Sorted Arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/
思路
总结一下,就是把求两个数组的中位数的问题,转化为求数组分割位置的问题。这是由于两个数组的长度固定,所以一个数组的分割长度知道了,可以求另一个数组的分割位置,根据
i + j == m - i + n - j (m+n为偶数)或者
i + j == m - i + n - j + 1 (m+n为奇数,这时i+j多一个数)
j = (m+n+1)/2 - i
需要注意的细节
1. 分割位置在头和尾的时候,该分割点不用动(估计这时候已经找到解了)
if i > 0 and nums1[i-1] > nums2[j]:
imax = i - 1
elif i < m and nums2[j-1] > nums1[i]:
imin = i + 1
2. 分割位置在头和尾的max_left和min_right要注意一下:
if i == 0:
max_left = nums2[j-1]
elif j == 0:
max_left = nums1[i-1]
else:
max_left = max(nums2[j-1], nums1[i-1])
AC代码
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m, n = len(nums1), len(nums2)
if m >= n:
m, n, nums1, nums2 = n, m, nums2, nums1
if m == 0:
if n % 2: return nums2[n/2]
else: return (nums2[n/2]+nums2[n/2-1])/2.0
imin, imax = 0, m
while(1):
i = (imin + imax) / 2
j = (m+n+1)/2 - i
if i > 0 and nums1[i-1] > nums2[j]:
imax = i - 1
elif i < m and nums2[j-1] > nums1[i]:
imin = i + 1
else:
if i == 0:
max_left = nums2[j-1]
elif j == 0:
max_left = nums1[i-1]
else:
max_left = max(nums2[j-1], nums1[i-1])
if (m+n) % 2 == 0:
if i == m:
min_right = nums2[j]
elif j == n:
min_right = nums1[i]
else:
min_right = min(nums2[j], nums1[i])
return (max_left+min_right)/2.0
else:
return max_left