查找给定列表中某些元素的所有索引.在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)索引查找.