04-median-of-two-sorted-arrays-寻找两个正序数组的中位数

问题

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1nums2 不会同时为空。

示例 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:
# 1. 下面这些情况进行处理
len1 = len(nums1)
len2 = len(nums2)
# 一个数组为空,补上另一个数组,中值/2后还是原来的结果(类似于: 3 * 2 / 2还是原来的结果)
if len1 == 0: nums1 = nums2
elif len2 == 0: nums2 = nums1
if len1 == 1 and len2 == 1: return (nums1[0] + nums2[0]) / 2 # 这个情况直接返回

# 2. 获取基本变量信息
lenAll = len1 + len2
mid = int(lenAll / 2 + 1) # 使运行到这里长度总>=3,mid中值的位置(3/2+1=2、4/2+1=3)
i = j = 0 # 便利索引
ary = [0, 0] # 存储中值的列表

# 3. 核心代码
while i < len1 and j < len2:
# 假定两个数字长度相同,和一个数组遍历到临界点的时候,刚好i + j == mid

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 # 达到中值 退出循环
# 对两个数组长度不一,以及一个数组下标i或j先行达临界点(nums1.length = i或nums2.length == j)进行补充
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

# 4. 判断后返回对应的运行结果
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/