查找给定列表中某些元素的所有索引。在 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 或散列 table，这样您就可以进行 O(log n) 次索引查找，而不是 O(n) 次。

Answer 2

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

您可以使用 merge sort 对列表进行 O(n log n) 时间的排序，如果您要查找的标记数组的长度是固定的，您将在 [=] 中进行固定数量的搜索11=].

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

Answer 3

这也可以在 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 returns 索引对应的对列表：

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].

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

Finding all the indexes of some elements on a given list. Can it be done in less than O(n^2) without arrays in Haskell?

arrays

haskell

list

array-algorithms