Haskell：两个整数列表之间的匹配数目？

问题描述：

4 12 24 26 35 41 

42 24 4 36 2 26

有两个列表之间的3场比赛。

如何计算匹配任何两个列表在Haskell之间有多少？

谢谢。

如果`2`在第二个名单是另一个`4`，会做4场比赛吗？如果第一个列表中的'12'也是另一个'4'，那么是否会进行6场比赛，4场比赛，还是只有3场比赛？ – dave4420 2011-12-15 11:13:45

对不起，我应该更清楚，列表不包含任何重复。我现在得到了我的答案，谢谢。 – Griffin 2011-12-15 11:15:15

答

如果您不需要照顾多个元素的，简单的方法是计算交叉口

import Data.List 

matches :: Eq a => [a] -> [a] -> Int 
matches xs ys = length (intersect xs ys)

某种程度上更高效的长度是用Set S作为中间结构，如果你也有一个Ord实例：

import qualified Data.Set as S 

matches :: Ord a => [a] -> [a] -> Int 
matches xs ys = S.size (S.intersection (S.fromList xs) (S.fromList ys))

如果你需要重复的护理，使用Map计数出现的每个元素的数量将是一个不太难的修改。

设置好的演示; Haskellers确实应该尝试更频繁地使用List之外的适当容器。 – 2011-12-15 21:12:57

答

这将与清单相当痛苦的你会需要通过他们所有对去。像这样的东西打印出正确的答案，形成所有对他们是平等的，然后计算大小。

let xs = [1,2,3,4] 
let ys = [1,2,3,4] 
length [x | x <- xs, y <- ys, x == y]

从性能的角度来看，这样做很尴尬。对于大的列表，你最好使用一组，你可以测试会员更快（通常是O（LG N），有时O（1））比你可以用列表（O（N））。

感谢您的回答。 – Griffin 2011-12-15 11:15:43

答

从Data.List函数intersect返回两个给定的列表之间的交叉点。

import Data.List (intersect) 

numberOfIntersections :: (Eq a) => [a] -> [a] -> Int 
numberOfIntersections xs ys = length $ intersect xs ys 

main = do 
    print $ numberOfIntersections [4, 12, 24, 26, 35, 41] [42, 24, 4, 36, 2, 26]

答

如果你想只使用列表的解决方案，这是不一样Data.List.intersect这么慢，你可以使用这个：

intersectSorted [] _ = [] 
intersectSorted _ [] = [] 
intersectSorted (x : xs) (y : ys) = case compare x y of 
    LT -> intersectSorted xs (y : ys) 
    EQ -> x : intersectSorted xs ys 
    GT -> intersectSorted (x : xs) ys 

intersect a b = intersectSorted (sort a) (sort b)

Haskell：两个整数列表之间的匹配数目？

相关推荐