首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

你会么?小弟我感觉很难-设计数据结构使得均摊成本为O(1)

2013-03-12 
你会么?我感觉很难---设计数据结构使得均摊成本为O(1)求解:有一个real number的set,两个操作:一个是find_m

你会么?我感觉很难---设计数据结构使得均摊成本为O(1)
求解:
有一个real number的set,两个操作:一个是find_min,一个是insert(X),删除的时候
要求是先把小于x的全删除了,然后再插入x,如何借助stack实现一个数据结构,使得两个操作
的均摊成本都是O(1).
[解决办法]
hint是,find_min就return stack.top();
这样的话insert基本就唯一解了。仔细想想就能写出来了。
[解决办法]

引用:
你的意思是用一个stack来存放sorted的数据?但是insert的amortized time怎么是o(1)呢?

每个元素进一次出一次。

热点排行