看板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