问题
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1
和 nums2
。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1
和 nums2
不会同时为空。
示例 1:
1 2 3 4
| nums1 = [1, 3] nums2 = [2]
则中位数是 2.0
|
示例 2:
1 2 3 4
| nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
|
代码题解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class Solution: def findMedianSortedArrays(self, nums1, nums2) -> float: len1 = len(nums1) len2 = len(nums2) if len1 == 0: nums1 = nums2 elif len2 == 0: nums2 = nums1 if len1 == 1 and len2 == 1: return (nums1[0] + nums2[0]) / 2
lenAll = len1 + len2 mid = int(lenAll / 2 + 1) i = j = 0 ary = [0, 0]
while i < len1 and j < len2:
if nums1[i] < nums2[j]: ary[(i + j) % 2] = nums1[i] i += 1 else: ary[(i + j) % 2] = nums2[j] j += 1 if i + j == mid: break while i + j < mid and i == len1: ary[(i + j) % 2] = nums2[j] j += 1 while i + j < mid and j == len2: ary[(i + j) % 2] = nums1[i] i += 1
if lenAll % 2 != 0: return ary[(i + j - 1) % 2] else: return (ary[0] + ary[1]) / 2
|
执行用时 :64 ms, 在所有 Python3 提交中击败了46.57%的用户
内存消耗 :13.8 MB, 在所有 Python3 提交中击败了6.15%的用户
参考:
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shu-zu-cun-chu-fa-jian-dan-yi-li-jie-on-by-guai-ma/