考虑以下函数:
import Data.List (find)
findInLists items = map $ find (`elem` items)
可以这样调用，结果如下:
findInLists [2,3] [[1,2], [1,3,2], [4, -2, 8]] -> [Just 2, Just 3, Nothing]
可以假定第一个参数已排序，但第二个参数不会排序。
如果 n 是要搜索的所有列表中的项目总数(在本例中为 7，因为一旦找到项目搜索就会停止)和 k 是要搜索的项目数，我相信这个函数的运行时间将是 O(n * k)。但是，当 n 也很大时，这对较大的 k 不利。
我希望运行时更像 O(n * log k) + O(k * log k) 或者如果可能的话更好。执行此操作的最佳方法是什么？
最佳答案
将 items 放入 Set 并使用 member .
关于algorithm - 在列表列表中快速查找，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12439919/