面試題目
給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 ..

如果輸入integer的最大bit數可以視為常數的話也許可以用bit值的字典樹型式來實現?

int 是 unsigned 32 bit 可以多給點 hint 嗎

想像一棵二元樹 遇0走左子樹 遇1走右子樹對於每個輸入數 讓他走這棵樹 路上沒節點就創節點走到底作標記(hash值 可用一個counter累加)這結構的空間正比於輸入數個數 查找為32次符合O(1)

簡單明瞭!!! 但這樣的缺點是什麼?

上網搜尋Minimal Perfect Hashing 應該有現成的方法吧..