在F#中如何对有序列表的连续数值进行分组

需求说明 #

给定已升序排序的F#整数列表，例如：[1; 2; 3; 5; 6; 20; 21; 22; 23]
要求将相邻差为1的连续数值分到同一组，预期输出：[[1; 2; 3]; [5; 6]; [20; 21; 22; 23]]
列表最大长度为1000条。

实现方案 #

因为输入已经预排序，最优方案为单次遍历实现，时间复杂度O(n)，空间复杂度O(n)，完全满足1000条数据的性能要求，无额外冗余开销。

F# 代码实现 #

let groupConsecutive (sortedList: int list) =
    match sortedList with
    | [] -> []
    | head::tail ->
        let (currentGroup, result) =
            tail
            |> List.fold (fun (current, acc) num ->
                // 直接取当前分组头部元素（最新加入的最大值）判断，避免遍历分组取末尾的O(k)开销
                if num = current.Head + 1 then
                    (num::current, acc)
                else
                    ([num], (List.rev current)::acc)
            ) ([head], [])
        // 拼接最后一个分组后反转整体顺序，和输入顺序保持一致
        List.rev ((List.rev currentGroup)::result)

调用测试 #

let input = [1; 2; 3; 5; 6; 20; 21; 22; 23]
let output = groupConsecutive input
// 输出结果：[[1; 2; 3]; [5; 6]; [20; 21; 22; 23]]

方案优势 #

• 纯函数式实现，符合F#惯用语法，无可变变量，可读性高
• 仅遍历列表1次，无额外排序、哈希计算等冗余操作，性能最优
• 边界处理完善，空列表、单元素列表等特殊场景都能正确返回

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