PAT 解题报告 1029. Median (25)

题目描述:

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

即找两个排序好的序列的中位数.

算法分析:

(1) 利用merge sort可过, O(N)时间复杂度

(2) 二分搜索, 每次比较两个有序数列的中间的数字, 类似二分查找可以砍掉一半一半, 如果两个中间的数字相等, 这个数字就是我们的中位数, 但是需要注意一些细节边界条件等等, 不太好实现, 复杂度O(logN).

(3) 利用寻找K-th 元素的算法, 比(2) 更容易实现

注意点:

没有坑点. 可以用归并排序AC

Written on August 1, 2013