中级编程通关练习题 #11 – 数列中值

给定两个已经从小到大排好序的整数数列 A 和 B,长度分别为 a 和 b。在时间复杂度为 O (log (a+b)) 的前提下,找出两个数列的中间值。也就是两个数列各自都只能遍历一次,找出它们的中值。所谓中值是指位置在两个数列中间的数值,如果 a+b的长度是9,那么中值就是两个数列合并后第五位置的数值,如果a+b的长度是10,那么中值就是第五和第六两个位置之和的一半。

输入样例:

A = [3, 5, 7, 9, 11]
B = [4, 6, 8, 10, 12]

输出样例:

7.5

在上面的输入样例中,两个数列合并后的数列是:[3, 4, 5, 6, 7, 8, 9, 10, 11, 12],数列的长度为10,那么中值就是第五、六位置之和的一半:(7 + 8)/ 2 = 7.5。

算法思路:

  • 这道题目的难点在于时间复杂度要求是 O (log (a+b)),也就是只能一次遍历。如果按照最简单的解决方法,就是先合并两个数列然后排序,但是这样的时间复杂度最少都是 n log(n),这样就不符合题目的要求。
  • 既然两个数列都已经排序完毕,那么我们可以把它当作是合并排序(merge sort)的第二步。首先合并两个数列,时间复杂度为 O (a+b)。
  • 数列合并后,如果数列的长度 K 是奇数,那么直接找到索引位置为 K/2 + 1 的数值。如果 K 是偶数,那么将索引位置 K/2 和 K/2 + 1 的两个数值相加然后减半。