PAT 解题报告 (数据结构学习与实验指导) 2-13. 两个有序序列的中位数

题目描述:

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A, A1…AN-1的中位数指A(N-1)/2的值,即第[(N+1)/2]个数(A为第1个数)。

算法分析:

(1) 这个题目要用类似二分法的思想去做, 实现细节其实很复杂而且很容易出bug, 大概的思想是这样: 比较两个list的中点, Amid 和 Bmid, 若Amid == Bmid, 那么这两个数字中的某一个就是题目中的median(按照题目的定义, 如果有其他定义的话可能要取这两个数字的平均), 若Amid < Bmid, 那么就去除Amid的前半个数组, 去除Bmid后面一半的数组, 那么类似的在剩下的一半数据里面再递归调用本身去搜那个median, 类似的Amid > Bmid的情况是对称的.

(2) 用在两个排序好的数组中找第k-th小的数的方法.

注意点:

二分法还是有点难实现, 注意边界和一些特殊case的判断和处理.

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 9, 2013