arrays - 查找给定列表上某些元素的所有索引。 Haskell 中没有数组的情况下可以在小于 O(n^2) 的时间内完成吗？

Question

给定 2 个唯一、可排序、不连续元素的列表，例如:

['d', 'a', 'z', 'b']

我想在另一个列表中找到他们的索引，例如:

['a', 'b', 'z', 'd']

结果将是一个包含其位置的列表:

[3, 0, 2, 1]  -- element at 0 is at 3,
              -- element at 1 is at 0, etc.

Answer 1

一个简单的解决方案是使用第二个列表创建 Data.Map 或哈希表，这样您就可以进行 O(log n) 次索引查找，而不是 O(n) 次索引查找。