时间戳

首页 > 解决方案 > 给定两个列表，将键值设置为最近的节点元素

list - 给定两个列表，将键值设置为最近的节点元素

问题描述

假设我有一个键列表， k = [2,3,7,15,18,23]; 和一个节点列表， n = [1,5,10,15,20]。两个列表都是排序列表。

那么“最近的下一个节点”，或者key的后继节点 k = 2 是 n = 5；因为 k = 3 是 n = 5；对于 k = 7 是 n = 10，等等。如果键值大于最后一个节点值，那么它的后继节点就是第一个节点元素，所以k = 23也是n = 1。我想输出一个列表数组，该数组将每个后继节点与其格式的键映射[[successor_node1, key, key],[successor_node2, key, key],...]。所以例如结果是output_array = [[5,2,3],[10,7,],[15,15],[20,18],[1,23]]

如何在一个函数中使用 F# 实现这些？

标签： listalgorithmarraylistf#

解决方案

您可以通过编写一个遍历两个列表并在第一个元素上进行模式匹配的递归函数来做到这一点。为了保持结果，最好的选择可能是使用不可变映射 - 在您进行操作时，您可以添加与各个后继节点关联的各个键的值：

let k = [2;3;7;15;18;23] 
let n = [1;5;10;15;20]

let rec findSuccessors first res k n =
  // Add a key 'k'  associated with a successor node 'n' to the list
  let add k n = 
    match Map.tryFind n res with
    | None -> Map.add n [n; k] res
    | Some l -> Map.add n (l @ [k]) res
  match k, n with 
  | [], _ ->  
    // If there are no more keys, we return the results
    res |> Map.toList |> List.map snd
  | k::ks, [] -> 
    // If there are no more successors, use the special 'first'
    findSuccessors first (add k first) ks []
  | k::ks, n::ns when n < k -> 
    // If we have a key 'k', but the next node is smaller, skip it
    findSuccessors first res (k::ks) ns
  | k::ks, n::ns -> 
    // Found a key 'k' with a successor 'n' - add it to the list
    findSuccessors first (add k n) ks (n::ns)

findSuccessors (List.head n) Map.empty k n

推荐阅读