一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 228|回复: 3
收起左侧

Fetching minimum with O(1)

[复制链接] |试试Instant~ |关注本帖
multics 发表于 2015-10-24 02:35:26 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@ - 网上海投 - 技术电面 |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本人最近电面碰到一个问题卡壳,求教群内高手。提问题的是一印度主管。

设计一个分配process id的方案,假设process id 从1开始,每次要新的process id时,求以最快的方法从未分配的数目中取得最小的process id,process id在使用结束后会放回未分配队列。

用priority queue/mini heap不是正确答案,因为取走最小的同时重新调整要化O(logn)的时间。考虑O(1)的方案,可以用sorted array/list, 那是把整理的开销O(n)延迟到process id 返回时。有没有可能使取走最小的为O(1), 放回已用的process id 为O(logn) 或O(1)? 谢谢。


withting 发表于 2015-10-24 02:43:45 | 显示全部楼层
难道是想问min stack?leetcode 原题
回复 支持 反对

使用道具 举报

zxl9171 发表于 2015-10-24 03:15:51 | 显示全部楼层
withting 发表于 2015-10-24 02:43
难道是想问min stack?leetcode 原题

不是minStack吧。minsatack只能知道最小,但是不能取走。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-10-24 09:27:32 | 显示全部楼层
应该可以用bitmap
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 06:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表