作者sandy4444 (質樸)
看板Prob_Solve
標題[討論] perfect hashing
時間Mon Nov 17 14:47:17 2014
面試題目
給N個(<1000) integer
給出一個 (min) perfect hashing
讓 N 個數儲存到 size 為 M 的array
(N<=M 他說可以的話讓 N=M)
達成之後 find 複雜度是O(1)
請問各位大大會選擇什方法
ps 小弟當下是用
0 = a * X^N + b * X ^(N-1) ....
1 = a * X^N + b * X ^(N-1) ....
.
.
.
N-1
把值帶進 X 然後去解 a b c ..
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 174.77.39.55
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1416206839.A.E07.html
※ 編輯: sandy4444 (174.77.39.55), 11/17/2014 15:06:18
1F：推 pika0923: 如果輸入integer的最大bit數可以視為常數的話 11/17 15:43
2F：→ pika0923: 也許可以用bit值的字典樹型式來實現? 11/17 15:43
3F：→ sandy4444: int 是 unsigned 32 bit 可以多給點 hint 嗎 11/17 15:53
4F：推 pika0923: 想像一棵二元樹 遇0走左子樹 遇1走右子樹 11/17 20:47
5F：→ pika0923: 對於每個輸入數 讓他走這棵樹 路上沒節點就創節點 11/17 20:48
6F：→ pika0923: 走到底作標記(hash值 可用一個counter累加) 11/17 20:48
7F：→ pika0923: 這結構的空間正比於輸入數個數 查找為32次符合O(1) 11/17 20:49
8F：→ sandy4444: 簡單明瞭!!! 但這樣的缺點是什麼? 11/18 03:34
9F：→ FRAXIS: 上網搜尋Minimal Perfect Hashing 應該有現成的方法吧.. 11/18 21:39