|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- [讨论]一道oxford计算机系算法设计题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=31345) |
|
-- 作者：aariel -- 发布时间：4/27/2006 9:25:00 AM -- [讨论]一道oxford计算机系算法设计题 you have a computer file containing 1,000,000 non-negative integers, in no particular order.?Imagine that they are the membership numbers of people who are enrolled in my internet club.?A new person wants to join the club, and we need to find an unused number to allocate to them.?How would you find, in a reasonable time, a number that was not already in the file? 大家什么想法？ |
|
-- 作者：Logician -- 发布时间：4/27/2006 1:17:00 PM -- 我觉得可以扫描一篇这个数组，记录其中最大的数（这只需要n次读取和n-1次比较），然后把这个数加1…… |
|
-- 作者：dyctomato -- 发布时间：4/28/2006 1:21:00 PM -- 题目意思就是找出不在这1,000,000个数的最小的正整数 有时间n空间1的算法 |
|
-- 作者：Logician -- 发布时间：4/28/2006 1:30:00 PM -- 一定要是最小的正整数吗？ |
|
-- 作者：dyctomato -- 发布时间：4/29/2006 9:38:00 PM -- 不一定要最小 只要在1～size里找个没有的就行，反正找最小的也不会需要更多的时间或空间 你的方法要是MAXINT在那些非负整数里怎么办？ |
|
-- 作者：Logician -- 发布时间：4/30/2006 5:41:00 PM -- MAXINT在那些非负整数里没关系，因为我取的是“MAXINT+1”…… |
|
-- 作者：Logician -- 发布时间：5/1/2006 3:45:00 PM -- 不过我想不出能在O(N)时间O(1)空间能找出最小的不在数组里的编号的方法。 能说说你的办法吗？ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
95.703ms |