看板Programming
标 题Re: [问题] 演算法
发信站中央资管龙猫资讯天地 (Tue Jan 16 23:20:13 2007)
转信站ptt!ctu-reader!ctu-gate!news.nctu!news.ncu!news.mgt.ncu!bbs
==> [email protected] () 提到:
: ※ 引述《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?
: : --
: : ◆ 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 根本就是一读完档就找到了
用2个 linking list
一个有用过
一个没用过
就可以啦
--
◎
龙猫资讯天地(
bbs.mgt.ncu.edu.tw)
◎[
brucetsao]From: 61-216-17-127.dynamic.hinet.net
1F：推 march20:是没错, 但还是要把该二 linked List 从 71.136.246.145 01/17 02:17
2F：推 march20:档案里读出来. 如果本来就有 maintain 这 71.136.246.145 01/17 02:18
3F：推 march20:两个 list 自然是可喜可贺 71.136.246.145 01/17 02:19
4F：推 march20:而且如果 unused list 已经空了的话, 你还 128.54.46.187 01/17 05:18
5F：推 march20:是得想个类似的方法, 可能是 max+1, 或是 128.54.46.187 01/17 05:19
6F：推 march20:sorted list 128.54.46.187 01/17 05:19
7F：→ qrtt1:范围很巨大用 link 会跑很久呗 :P 163.26.34.20 01/17 08:18
8F：→ qrtt1:指标多起来用到的空间也很可怕 163.26.34.20 01/17 08:19
9F：推 ephesians:无限的自然数怎麽用linked list?218.160.109.107 01/17 12:21