algorithm - 在线性时间内找到两个排序列表中的公共(public)元素

Question

我有一个排序的输入列表:

let x = [2; 4; 6; 8; 8; 10; 12]
let y = [-8; -7; 2; 2; 3; 4; 4; 8; 8; 8;]

我想编写一个行为类似于 SQL INNER JOIN 的函数。换句话说，我想返回 x 和 y 的笛卡尔积，它只包含两个列表中共享的项目:

join(x, y) = [2; 2; 4; 4; 8; 8; 8; 8; 8; 8]

我写了一个简单的版本如下:

let join x y =
    [for x' in x do
        for y' in y do
            yield (x', y')]
    |> List.choose (fun (x, y) -> if x = y then Some x else None)

它有效，但它在 O(x.length * y.length) 中运行。由于我的两个列表都已排序，我认为可以在 O(min(x.length, y.length)) 中获得我想要的结果。

如何在线性时间内找到两个排序列表中的共同元素？

Answer 1

我无法在 F# 方面为您提供帮助，但基本思想是使用两个索引，每个索引一个。在该列表的当前索引处选择每个列表中的项目。如果这两个项目的值相同，则将该值添加到结果集中并递增两个索引。如果项目具有不同的值，则仅增加包含两个值中较小值的列表的索引。重复比较，直到你的一个列表为空，然后返回结果集。