Re: [問題] 演算法
※ 引述《march20 ()》之銘言:
: ※ 引述《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 根本就是一讀完檔就找到了
換題目玩玩。
如果我們不要走漏洞,而是真的當作是實用的情況,然後把題目修改一點,
必須要找出最小、而又沒有被使用的數字,那麼除了排序之外,還有沒有其
他更快捷的方法?
討論區真的有這個問題。就是十萬個用戶,注冊了從 1到100000的 UID,然
後版主刪掉中間五萬名會員,所以就零零散散地斷層了。如果新用戶注冊,
就必須用 100001 的UID。
如果是這樣的問題,除了排序之外,還有沒有別的辦法?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.50.36.148
推
01/16 16:35, , 1F
01/16 16:35, 1F
討論串 (同標題文章)