请教个算法

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

请教个算法

发表于：2008-01-22 11:06:25 楼主

两个线性表a，b，a，b都无序，a比较大（5w左右），b是a的子集，比较小（5k以下），现在要快速确定b中每个元素在a中的顺序，有什么好算法

发表于：2008-01-22 11:19:561楼得分:0

带连接的散列。
1、先将一个散列表全部赋0
2、将b中的元素散列，对应位置赋1，并在散列表中记录在b中的位置
3、对a散列，若对应的散列表所在位置为1，那么……自己想吧

就是这样，复杂度o（m+n)

发表于：2008-01-22 14:12:002楼得分:0

有道理

发表于：2008-01-22 20:02:503楼得分:0

用了哈希表，有更好的算法吗

发表于：2008-01-22 20:29:034楼得分:0

无序就这样了

发表于：2008-01-23 10:51:485楼得分:0

哈希就是空间换时间，如果想剩点空间可以用二叉排序树，不过时间复杂度要上升到log级别，如果一点辅助空间都不用的话，就得是m*n的复杂度。如果a特别特别的大，又想省点空间的话，那可以考虑布隆过滤器。

发表于：2008-01-23 10:58:086楼得分:0

谢谢你的建议，布隆过滤器应该不错。

其他资讯