https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

代码:

# -*- coding:utf-8 -*-
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""

def findKthElement(arr1, arr2, k):
"""
寻找第k个元素
:param nums1:
:param nums2:
:param k:
:return:
"""
l1, l2 = len(arr1), len(arr2)
if l1 > l2:
return findKthElement(arr2, arr1, k)
if not arr1:
return arr2[k - 1]
if k == 1:
return min(arr1[0], arr2[0])
value1 = min(k // 2, l1) - 1
value2 = min(k // 2, l2) - 1
if arr1[value1] > arr2[value2]:
return findKthElement(arr1, arr2[value2 + 1:], k - value2 - 1)
else:
return findKthElement(arr1[value1 + 1:], arr2, k - value1 - 1)

ll1, ll2 = len(nums1), len(nums2)
left, right = (ll1 + ll2 + 1) // 2, (ll1 + ll2 + 2) // 2
return (findKthElement(nums1, nums2, left) + findKthElement(nums1, nums2, right)) / 2.0


if __name__ == '__main__':
nums1 = [1, 3]
nums2 = [2]
print(Solution().findMedianSortedArrays(nums1, nums2))

思路:一般这种题做法还是比较简单的,依次遍历两个列表就可以找到中位数,复杂度在O(m+n),但是这道题限制在log(m+n)的时间内完成,所以需要使用二分查找。我们对每个列表检查第k/2位(k为中位数下标),对于较小的那个列表,我们可以确定前k/2个数都不会是中位数,因此可以将前k/2个数整体删掉继续递归。

边界条件就是其中一个列表被删完了或者需要取最小的元素,只须比较一下两个列表的0号元素输出即可。

分类: 算法

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注