面试题目
给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 应该有现成的方法吧..