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

Question

We have three lists which contain people's names.

All three lists have been sorted alphabetically.

Now we need to find at least one name which appear in all three lists.

---

我想的算法是这样的:

I get three heads out of three lists.

if the three heads are not equal to each other, then I keep the max one and get two new heads from the lists from which I just dropped the heads.

Continue above procedure until I find such an element as described in the beginning.

这个算法正确吗？

---

问题是我不确定如何使用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