sbiwwk
幼苗
共回答了17个问题采纳率:82.4% 举报
你说的是在广搜中的去重吧,那就是弄一个哈希表,把每步搜出来的结果hash一下,然后存在hash表中,如果发现要存的地方已经有了,如果相同,就不存,不同,就用链表法把他们链起来.
具体不好表达,或是说我表达能力有限,举个简单例子.
我有几个数,{1,2,3,4,5,6,7,8,9,10,1,12,13}
定义一个hash函数 f(x) = x (如果x范围很小,可以直接这么弄,这样不会引起冲突,否则需要弄取模之类的hash函数了,具体你还是要去看看书之类的)
那么定义个hash表
hash=array[1..n]of boolean , n为最大范围
那么每次加入的时候直接判断hash[x]是不是真就可以了,是真的话,就是重了
否则,记录hash[x]为真
1年前
追问
1
举报
sbiwwk
hash可以说是效率最高的集合处理方式了,去重一般首选他,一般来说,一个好的hash函数的去重操作复杂度是常数级的. 其他去重方式也有,比较常用的还有 康托展开