作者march20 ()
看板Programming
标题Re: [问题] 演算法
时间Sat Jan 13 12:30:19 2007
※ 引述《yaote (ted)》之铭言：
: 标题: [问题] 演算法
: 时间: Sat Jan 13 11:16:10 2007
:
:
: 以下是一所国外研究所的考试题目，是否能用程式跟图解来解答这个问题?
:
: I 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?
:
:
: --
:
※ 发信站: 批踢踢实业坊(ptt.cc)
: ◆ From: 220.140.56.26
: 推 march20:全部加起来一定没问题 XD 71.136.235.216 01/13 11:58
: 推 march20:如果只需要一次的话. 71.136.235.216 01/13 11:59
: 推 march20:不然长远来看, 用些资料结构来放会比较赚 71.136.235.216 01/13 11:59
: 推 march20:喔, 为了避免 0 的问题, sum 完後再加1 71.136.235.216 01/13 12:07
马上发现其实我想太麻烦了 (虽然那也是第一时间想到的)
只要找到 max 再加一就好.
max 根本就是一读完档就找到了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.136.235.216
1F：推 idicivik:这样可能会有问题吧 如果max 是1000000 될 140.112.50.171 01/13 15:01
2F：推 march20:原题没给限制哩 (事实上给 float 也可啊XD 71.136.235.216 01/13 15:09
3F：推 idicivik:题目有提到ㄟ nonegative integer 140.112.50.171 01/13 15:12
4F：推 march20:请看上一篇 :P 71.136.235.216 01/13 15:14
5F：推 Eventis:这是有问题的,既然都说是在电脑里读档了. 61.64.152.7 01/13 16:55
6F：→ Eventis:就会有overflow的问题. 61.64.152.7 01/13 16:55
7F：→ Eventis:就算传负值也会牵涉到data type....@@ 61.64.152.7 01/13 16:56
8F：推 march20:我觉得可以不用考虑 overflow, 因为都写在 71.136.235.216 01/13 17:29
9F：推 march20:档案里了, 就再进一位也是还好 71.136.235.216 01/13 17:29
10F：推 march20:找 max 也只需要记目前最大值, 位数再多 71.136.235.216 01/13 17:30
11F：推 march20:linked list 就搞定了. 71.136.235.216 01/13 17:31
12F：推 march20:(没说是什麽样的 file, 就随人解释吧, 71.136.235.216 01/13 17:33
13F：推 march20:我就当这些数字存成字串了 ) 71.136.235.216 01/13 17:34