如何用单个F#函数实现有序key到最近后继node的分组映射

实现思路 #

题目给出的key列表与节点列表均为预排序的升序列表，我们采用双指针思路实现线性时间复杂度计算：遍历key的同时维护节点指针的位置，指针无需回溯，整体时间复杂度为O(m+n)，其中m为key数量，n为节点数量。

完整代码 #

let getSuccessorGroups (sortedKeys: int list) (sortedNodes: int list) =
    // 入站校验
    if sortedNodes.IsEmpty then invalidArg (nameof sortedNodes) "节点列表不可为空"
    let nodeCount = sortedNodes.Length
    // fold状态：(当前节点指针位置, 已收集的<后继节点, key>配对列表)
    (0, [])
    |> List.fold (fun (curNodeIdx, pairs) key ->
        // 移动指针找到第一个大于当前key的节点
        let rec moveNext idx =
            if idx >= nodeCount then idx
            elif sortedNodes.[idx] > key then idx
            else moveNext (idx + 1)
        let newNodeIdx = moveNext curNodeIdx
        // 超出节点列表长度则取第一个节点作为后继
        let successor = if newNodeIdx >= nodeCount then sortedNodes.[0] else sortedNodes.[newNodeIdx]
        (newNodeIdx, (successor, key) :: pairs)
    ) sortedKeys
    |> snd
    |> List.rev // 恢复key的原始顺序
    |> List.groupBy fst // 按后继节点分组
    |> List.map (fun (succ, group) -> succ :: (group |> List.map snd)) // 转换为要求的列表格式
    |> List.toArray // 输出为数组

测试用例 #

// 题目给出的示例输入
let k = [2;3;7;15;18;23]
let n = [1;5;10;15;20]
// 调用函数
let output = getSuccessorGroups k n

输出结果 #

output的值为 [|[5; 2; 3]; [10; 7]; [15; 15]; [20; 18]; [1; 23]|]，完全符合题目要求的输出格式。

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