目录
  1. 1. 题目
  2. 2. DEMO
  3. 3. 解法
    1. 3.1. 合并计算长度取值
    2. 3.2. 分别取中值(二分法)
findMedianSortedArrays

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

DEMO

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0


nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解法

合并计算长度取值

nums1nums2合并为一个new_nums,计算新数组的长度,然后再直接取值是中间的数还是中间两个数的平均数。

  • LeetCode结果116ms/11.9MB
  • 复杂度达标:否
1
2
3
4
5
6
7
8
9
10
def findMedianSortedArrays(nums1, nums2):
new_list = nums1 + nums2
length = len(new_list)
new_list.sort()
if length%2:
if length == 1:
return new_list[0]
return new_list[length//2]
else:
return (new_list[length/2-1]+new_list[length/2])/2.0

分别取中值(二分法)

步骤:

  1. nums1的中值,nums2的中值对比
  2. 将较小的一方包含中值在内的数移除,并记录计数器del_nums_count
  3. 对比del_nums_count的大小和中位数的索引k(索引固定为num1+nums2长度的中间值或中间两个值),如果del_nums_count的长度已经大于了k,则需要在此次将要移除的子数组中进行取索引定位;反之,继续执行2
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
def findMedianSortArrays(nums1, nums2):
nums1_length = len(nums1)
nums2_length = len(nums2)

# 计算中位数k的索引
if (nums1_length+nums2_length)%2:
k = (nums1_length+nums2_length)//2
else:
k = (nums1_length+num2_length)/2+0.5

remove_nums_count = 0
while True:
if nums1[nums1_length//2] >= nums2[nums2_length//2]:
remove_nums = num2[:num2_length//2+1]
if nums2_length//2+remove_nums_count >= k:
if k%2:
k_value = remove_nums[k-remove_nums_count]
else:
k_value = (remove_nums[k-remove_nums_count-1]+remove_nums[k-remove_nums_count])/2.0
break
else:
remove_count = num2_length//2+1
nums2_length //= 2
else:
remove_nums = num1[:num1_length//2+1]
if nums1_length//2+remove_nums_count >= k:
if k%2:
k_value = remove_nums[k-remove_nums_count]
else:
k_value = (remove_nums[k-remove_nums_count-1]+remove_nums[k-remove_nums_count])/2.0
break
else:
remove_count = num1_length//2+1
nums1_length //= 2
文章作者: ZyTomorrow
文章链接: https://zytomorrow.top/2019/06/10/leetcode/findmediansortedarrays/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tomorrow
打赏
  • 微信
  • 支付寶

评论