【LeetCode每天一题】Median of Two Sorted Arrays（两数组中的中位数）

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)). You may assume nums1 and nums2 cannot be both empty.

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

解决思路

　　假设两个数组合并后的总长度 L，并且每个数组中的元素都是有序的，我们可以使用二分查找的思路。　　

　　第一种解决办法（二分查找）：如果我们取出nums1[i] ，用二分查找在数组 nums2中找到 nums1[i] 可以插入的位置，假设 nums1[i] 在 nums2 中的插入位置是 j，那么 A[i] 在整个合并数组中的位置就是 (i + j) ，因为要求的中位数的位置是 L / 2，通过比较 (i + j) 和 L / 2 的大小可以每次舍弃 nums1的一部分，从而减小每次处理的数量。用同样的方法可以收敛数组 nums2。但是这样的复杂度是 O(log m *log n)，复杂度大于 O(log(m + n))，显然不是最优的。　　

　　使用二分查找的思想进行优化：要求找到两个数组合并之后的中位数，就是要找第 k 大的数（k = (L / 2 + 1)，而当 L 是偶数时，要求第 (L / 2) 大和第 (L / 2 + 1) 大的两个数。当我们舍弃掉一部分，假设舍弃部分的长度为 length，那么接下来就是在剩下的数组里求第 (k - length) 大的数。逐层缩小范围，直到两数组其中一个走完。既然是要找合并后的数组 nums 中第 k 大元素，即 nums[k-1]，那如果我们从 nums1 和 nums2 中分别取前 k/2 个元素，其中必然有一部分是在数组 nums 的前 k 个数里。设 mid = k / 2，当 nums1[mid - 1] < nums2[mid - 1] 时，可以断定 nums1 的前 mid 个元素是在 nums 的前 k 个数里，那么我们则舍弃 nums1 的前 mid 个元素。反之则舍弃 nums2 的前 mid 个元素。现在数组 nums1 或者nums2 已经舍弃掉 k/2 个元素，缩小查找范围了，按照上面的方法继续递归选择下去，直到找到目标元素。

复杂度

　　时间复杂度为O(log m+n), 空间复杂度为O(1)

图示步骤

代码

 class Solution(object):

     def findMedianSortedArrays(self, nums1, nums2):

         """

         :type nums1: List[int]

         :type nums2: List[int]

         :rtype: float

         """

         n1, n2 = len(nums1), len(nums2)

         if len(nums1) ==  and len(nums2) == :     # 如果两个数组中元素个数都为0，则直接返回

             return 0.0

         total = n1+n2                               # nums 总长度

         if total %:

             return self.Kth_larget(nums1, nums2, total//2 +1) # 如果总长度为基数，则直接求中间元素

         else:

             a = self.Kth_larget(nums1, nums2, total//2)        # 总长度为偶数，求两个元素，并相加除以2

             b = self.Kth_larget(nums1, nums2, total//2+1)

         return (a+b)/2.0

     def Kth_larget(self, n1, n2, kth):

         n1_len,n2_len = len(n1), len(n2)                      # 两个数组的列表长度

         if n1_len ==  or n2_len == :                        # 如果其中一个数组为空，则直接返回另一个数组中第k个元素。

             return n2[kth-] if n1_len ==  else n1[kth-]

         if kth == :                                          # 如果k等于1，则直接返回两个数组中首部最小的元素

             return min(n1[], n2[])

         mid = kth//2                                           # 中间值

         a,b = float('inf'), float('inf')

         if n1_len >= mid:                                      # 求nums1 中的当前中间值

             a = n1[mid-]

         if n2_len >= mid:                                       # 求nums2 中的当前中间值

             b = n2[mid-]

         if a < b:                                               # 然后比较中间值的大小，从而选择剔除的一部分。

             return self.Kth_larget(n1[mid:], n2, kth-mid)

         else:

             return self.Kth_larget(n1, n2[mid:], kth-mid)

巴特西

【LeetCode每天一题】Median of Two Sorted Arrays（两数组中的中位数）

最新文章

热门文章