作者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/cn.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