题目

给定两个大小为 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
相关文章
评论
分享
  • lengthOfLongestSubstring

    题目 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 DEMO 输入: “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 输入: “bbbbb”输出: 1解释: 因...

    lengthOfLongestSubstring
  • addTwoNumbers

    题目 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 ...

    addTwoNumbers