2

一意で、順序付け可能で、連続していない要素の 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.
4

3 に答える 3

6

簡単な解決策の 1 つは、2 番目のリストを使用して Data.Map またはハッシュ テーブルを作成し、O(n) インデックスの代わりに O(log n) インデックス ルックアップを作成することです。

于 2015-02-27T00:06:02.690 に答える
3

これはO(n log n)、いくつかの種類で時間内に行うこともできます。2 番目のリストは最初のリストの順列であると想定しています。

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

于 2015-02-27T07:33:36.560 に答える
0

最初に、宛先配列内のすべての文字のマップを作成する必要があります。次に、2 つのオプションがあります。

マージソートを使用してリストをO(n log n)時間順に並べ替えることができます。探しているトークンの配列が一定の長さである場合は、 で一定数の検索を行いO(log n)ます。

もう 1 つの解決策は、目的の配列を取得し、それをすべてハッシュ マップに配置してから、そこで検索することです。

于 2015-02-27T00:11:32.553 に答える