algorithm - 在 OCaml 的所有三个列表中找到至少一个元素

Question

我们有三个包含人名的列表。

所有三个列表都按字母顺序排序。

现在我们需要找到至少一个出现在所有三个列表中的名称。

---

我想的算法是这样的：

我从三个列表中得到三个正面。

如果三个头彼此不相等，那么我保留最大的一个并从我刚刚丢弃头的列表中获得两个新头。

继续上面的过程，直到我找到开头描述的这样一个元素。

这个算法正确吗？

---

问题是我不确定如何使用 ocaml 来编写函数。

Answer 1

这是一个 OCaml 函数，它使用您的算法对两个排序列表进行交集（这确实是解决这个问题的好方法）。

let rec intersect l1 l2 = match l1, l2 with
| [], _ | _, [] -> []
| h1 :: t1, h2 :: t2 ->
  if h1 < h2 then intersect t1 l2
  else if h1 = h2 then h1 :: (intersect t1 t2)
  else intersect l1 t2

Answer 2

Thomash 的算法将通过两次调用intersect和创建中间列表来完成这项工作，因此效率不高。

你的算法基本上是正确的。额外的一点是，有时你有两个头等于最大值，你应该只放下剩下的头。

这是用 OCaml 编写的修改后的算法：

let rec intersect xs ys zs =
    match xs, ys, zs with
    | [], _, _ | _, [], _ | _, _, [] -> None
    | x::xs', y::ys', z::zs' -> 
       if x = y && y = z then Some x
       else 
           let m = max x (max y z) in
           if x = m && y = m then intersect xs ys zs'
           else if x = m && z = m then intersect xs ys' zs
           else if y = m && z = m then intersect xs' ys zs
           else if x = m then intersect xs ys' zs'
           else if y = m then intersect xs' ys zs'
           else intersect xs' ys' zs