OCaml实现：寻找有序列表中最小的缺失正整数

首先得说，你现有的代码在不少场景下已经能给出正确结果了，比如你测试的那几个用例都没问题！不过我注意到它还没覆盖一些边界情况，咱们来一步步完善它。

先看看你当前的实现：

let getMissingNumber l = 
  let rec find min = function 
    | [] -> min 
    | t :: [] -> t + 1 
    | t1 :: t2 :: r -> if t2 - t1 > 1 then t1 + 1 else find min (t2 :: r) 
  in find 1 l;;

现有代码的局限 #

比如这些场景下，结果会不符合预期：

• 当列表从大于1的数开始时：getMissingNumber [2;3;4]会返回5，但正确结果应该是1（因为1是大于0且缺失的最小数）
• 当列表包含负数或0时：getMissingNumber [-1;0;2]会返回3，但正确结果是1
• 虽然重复元素场景下原代码碰巧能生效，但逻辑上没有特意处理这类情况

改进后的实现 #

我们可以调整思路：先过滤掉所有非正数（毕竟只关心大于0的数），然后跟踪「当前期望的最小缺失数」（初始为1），逐个检查列表元素：

let getMissingNumber l =
  (* 先过滤出所有大于0的数，原列表有序，过滤后依然保持有序 *)
  let positive_numbers = List.filter (fun x -> x > 0) l in
  let rec find expected = function
    | [] -> expected  (* 列表遍历完，当前期望的数就是缺失的 *)
    | hd :: tl ->
        if hd = expected then
          (* 当前数存在，期望数加1，继续找下一个 *)
          find (expected + 1) tl
        else if hd > expected then
          (* 当前数比期望的大，说明期望的数就是缺失的最小数 *)
          expected
        else
          (* 处理重复元素（比如[1;1;2]），直接跳过当前元素，继续检查下一个 *)
          find expected tl
  in find 1 positive_numbers

测试各种场景 #

现在这个版本能覆盖所有情况了：

• getMissingNumber [1;4;5] → 2 ✔️
• getMissingNumber [1;2;5] → 3 ✔️
• getMissingNumber [1;2;3] → 4 ✔️
• getMissingNumber [2;3;4] → 1 ✔️
• getMissingNumber [-2;-1;0] → 1 ✔️
• getMissingNumber [0;1;2] → 3 ✔️
• getMissingNumber [1;1;2] → 3 ✔️
• getMissingNumber [] → 1 ✔️

为什么原代码会有问题？ #

原代码里的t :: [] -> t + 1分支是硬返回了最后一个元素+1，没有考虑到「最后一个元素之前已经有缺失的数」或者「整个列表都比初始的min（1）大」的情况。调整后的递归逻辑更灵活，始终跟踪我们要找的最小缺失数，就不会出现这类问题啦。

内容的提问来源于stack exchange，提问作者AlexT