找到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