如何快速找出两个队列中相同的元素，假设队列的长度非常大

之前面试腾讯时，遇到一道面试题。
题目大概是假设有海量的QQ会员参加了活动A，也有海量的QQ会员参加了活动B，如何快速找出既参加了活动A，又参加了活动B的QQ会员？

当时回答时答得乱七八糟的，哎...

我暂时想到的方法是先将两个队列变为有序队列，然后分别从两个队列的头部开始迭代：

如果两个队列的当前元素大小相等，则两个队列的遍历下标分别前移1；否则将指向较小元素的下标前移1，另一个下标不变。

这样遍历一直到其中一个队列已经完全遍历为止。这时便能找出所有相同的元素。

算法一直是自己短板。暂时想不出更好的办法，要是不用排序就好了。  

评论

3 楼 moxiaomomo 2011-05-03  

用hash表找吧，把第一个活动的会员用QQ号生成hashcode，放入Hash表中，
对于第二个列表遍历一次，每个去那个hash表中是否有值。
所要花费的时间为，第一个活动列表一次hash计算过程。
第二个活动列表的hash计算过程。

BootsLee.NewBegin 写道

用hash表找吧，把第一个活动的会员用QQ号生成hashcode，放入Hash表中，
对于第二个列表遍历一次，每个去那个hash表中是否有值。
所要花费的时间为，第一个活动列表一次hash计算过程。
第二个活动列表的hash计算过程。

恩恩，有道理~~但如果是海量数据的话，在控制hash碰撞的概率方面会不会有点麻烦？

2 楼 BootsLee.NewBegin 2011-04-27  

用hash表找吧，把第一个活动的会员用QQ号生成hashcode，放入Hash表中，
对于第二个列表遍历一次，每个去那个hash表中是否有值。
所要花费的时间为，第一个活动列表一次hash计算过程。
第二个活动列表的hash计算过程。

1 楼 234390216 2011-04-27  

既然有记录的，那么表里面应该会有记录的，可以利用表连接来做吧！