PAT 解题报告 1057. Stack (30)

题目描述:

设计一个类似栈的数据结构, 支持一般的push 和 pop, 同时附加一个find median 的功能.

算法分析:

除了stack以外, 维护一些其他的数据结构, mid 总是存那个median的值, 一个c++的multiset (叫做uppers) 存所有比mid大的数字, 另一个multiset (lowers) 存比mid小的那些数字. push的时候要根据push的值比当前mid大还是小插入到对应的uppers或者lowers, 同时根据两个set的大小对mid, lowers, uppers大小进行必要的调整, 为了保证mid是真正的median值, uppers的大小应该是和lowers大小一样或者只是比lowers大一个单位, 我们这里需要的是插入 delete, 查找任意元素的时间都合理, 那么multiset就是最好的选择了, 因为他本质上是一颗平衡树, 增, 删, 查都是log N时间, 还有个好处是常数时间能到到最大最小值的的值以及位置. 这样下来基本上push 的时间是log N, pop的时间也是log N, find median 的时间是常数时间, 因为我们总是维护好mid这个变量。

注意点:

如上

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


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

Written on April 7, 2013