两个排序数组的中位数
中英题面
给定两个大小为 m 和 n 的有序数组nums1和nums2。
There are two sorted arraysnums1andnums2of size m and n respectively.
请找出这两个有序数组的中位数。要求算法的时间复杂度为O(log (m+n)) 。
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
示例 1:
nums1 = [1, 3] nums2 = [2] 中位数是 2.0
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5<br /><br /><br />
算法
将原题转化为在两个有序数列中查找第k小的元素。
对于长度为m和n的两个有序数列a和b,考虑0 < i < m和0 < j < n且i + j + 2 == k。
若a[i] < b[j],则a[0..i]与b[j..(n – 1)]中比无所要查找的元素,将其删去后更新k值递归处理。
时间复杂度:
O(log(M + N))
空间复杂度:
O(log(M + N))
代码
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ m = len(nums1) n = len(nums2) s = m + n + 1 return (self.findKth(nums1, nums2, s // 2) + self.findKth(nums1, nums2, s - s // 2)) / 2 def findKth(self, nums1, nums2, k): m = len(nums1) n = len(nums2) if (m < n): return self.findKth(nums2, nums1, k) if (not n): return nums1[k - 1] if (k == 1): return min(nums1[0], nums2[0]) mid1 = max(k * m // (m + n) - 1, 0) mid2 = k - mid1 - 2 if (nums1[mid1] < nums2[mid2]): return self.findKth(nums1[mid1 + 1 :], nums2[: mid2 + 1], k - mid1 - 1) if (nums1[mid1] > nums2[mid2]): return self.findKth(nums1[: mid1 + 1], nums2[mid2 + 1 :], k - mid2 - 1) return nums1[mid1]
相关推荐
randy0 2020-11-17
lixiaotao 2020-10-07
美丽的泡沫 2020-09-08
nongfusanquan0 2020-08-18
hang0 2020-08-16
earthhouge 2020-08-15
算法改变人生 2020-07-28
troysps 2020-07-19
Broadview 2020-07-19
chenfei0 2020-07-18
风吹夏天 2020-07-07
yangjingdong00 2020-07-05
数据与算法之美 2020-07-05
shawsun 2020-07-04
数据与算法之美 2020-07-04
要知道时间复杂度只是描述一个增长趋势,复杂度为O的排序算法执行时间不一定比复杂度为O长,因为在计算O时省略了系数、常数、低阶。实际上,在对小规模数据进行排序时,n2的值实际比 knlogn+c还要小。
Evankaka 2020-07-04
田有朋 2020-06-28