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) 索引查找。

Answer 2

这也可以通过O(n log n)几种方式及时完成。我假设第二个列表是第一个列表的排列。

import Data.List
import Data.Ord
import Data.Function

correspIx :: Ord a => [a] -> [a] -> [(Int, Int)]
correspIx = zip `on` map fst . sortBy (comparing snd) . zip [0..]

correspIx返回具有彼此对应的索引的对列表：

correspIx "dazb" "abzd" == [(1,0),(3,1),(0,3),(2,2)]

我们需要另一种排序来获得问题中指示的结果：

correspIx' :: Ord a => [a] -> [a] -> [Int]
correspIx' xs ys = map snd $ sortBy (comparing fst) $ correspIx xs ys

现在correspIx' "dazb" "abzd" == [3,0,2,1]。

Answer 3

首先，您必须创建目标数组中所有字符的映射，然后您有两个选择：

您可以使用归并排序及时对列表进行排序O(n log n)，如果您要查找的标记数组的长度是恒定的，那么您将在O(log n).

另一种解决方案是获取目标数组并将其全部放入哈希映射中，然后在那里搜索。