求算法。

rmg_mage

题外话：你们为什么不去向NOI提出加入RUBY编程计划？

Cola酱

回复 紫苏 的帖子
关于桶排：
桶排序要把同一个桶里面的东西链在一起
比如说在"1"桶里面是1：1.1->1.4->1.7
不过如果数字都是整数的话
那么就变成了1: 1->1->1
这样就是HASH表的原形
但是因为Hash(X)=Hash(Y)不可推出X=Y
所以才要有解决冲突
这就是完整的HASH表
至少我就是这么认为的


关于哈希碰撞：
首先Hash(X)=Hash(Y)不可推出X=Y
但是Hash(X)!=Hash(Y)可推出X!=Y
所以对于字符串数组A的所有哈希值
只要通过二分查找 找到对应哈希值在B中的起始位置
就可以判定有没有同样字符串在B中出现
大概就是这样


不知道紫苏你是学什么语言的呢
我是PASCAL的 略懂一点C

紫苏

回复 Cola酱 的帖子

桶排序使用的桶都是长度固定的数组吧，至少我还没见过用链表实现桶的。散列表有一个装载因子，就是元素个数/桶数组大小的比率，这里也是使用的固定大小的一个桶，因为只有顺序结构才能用 O(1) 时间访问。我觉得你说的是每个桶的空位，如果使用分离链接法，那这些空位确实是要指向一个链式结果，所有碰撞了的键的值都被链在这里。如果这里用二叉搜索树，就同时保证了节点顺序，散列表就可以在 O(log n) 内完成查找，但这并非桶排序。

首先Hash(X)=Hash(Y)不可推出X=Y
但是Hash(X)!=Hash(Y)可推出X!=Y
所以对于字符串数组A的所有哈希值
只要通过二分查找 找到对应哈希值在B中的起始位置
就可以判定有没有同样字符串在B中出现

嗯，那要带着键和值一起排序，才能在冲突的时候判断是否值相等。不过当你排好两个数组 C、D 的顺序后，做一个从左到右判断就够了——假设 i 是循环变量，我们要进行 C - D 这个有方向差集运算，因为已经排好序，所以可以在迭代时判断 D[ｉ] 是否在 C[ｉ] 和 C[i+1] 之间（不含临界点），如果是，则说明 D[ｉ] 这个元素不在 C 中，以此类推，所以才有前面提到的 O(min(m,n))。冲突的情况，也是只能通过相邻键相同的值挨个比较，毕竟值没有顺序。

不知道紫苏你是学什么语言的呢
我是PASCAL的 略懂一点C

厉害，现在学 Pascal 的年轻人还真少见，我年轻的时候就完全没接触过 Pascal。我以前主要是搞 Java，后来注意力集中到了 C/C++。至于 Ruby，我从开始接触程序以后就一直在学，但到现在仍然是个半吊子，每天都需要灌输新的东西（这小妮子成长太快了！）。

moy

膜拜各位大神{:nm_3:}

Cola酱

回复 紫苏 的帖子

对哦
排序后都有单调性的
而且A与B求交集就是B与A的交集诶
话说我因为最近做的题目二分答案的太多了
心里有阴影了= =
一看到题目就想二分= =

那这样我就完全明白了
谢谢紫苏哈