在线性时间中查找两个排序列表中的公共元素

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#,但基本思路是使用两个索引,每个列表一个.在该列表的当前索引处选择每个列表中的项目.如果这两个项的值相同,则将该值添加到结果集中并递增两个索引.如果项目具有不同的值,则仅增加包含两个值中较小值的列表的索引.重复比较,直到其中一个列表为空,然后返回结果集.

Answer 2

O(min(n,m))时间是不可能的:取两个列表[x; x; ...; x; y]和[x; x; ...; x; z].您必须浏览两个列表直到结束才能比较y和z.

即使O(n + m)也是不可能的.取[1,1,...,1] - n次和[1,1,...,1] - m次然后结果列表应该有n*m个元素.你需要至少O(nm)(正确的Omega(nm))时间来创建这样的列表.

没有笛卡尔积(简单合并),这很容易.Ocaml代码(我不知道F#,应该合理地关闭;编译但未测试):

let rec merge a b = match (a,b) with
   ([], xs) -> xs
|  (xs, []) -> xs
|  (x::xs, y::ys) -> if x <= y then x::(merge xs (y::ys))
                else y::(merge (x::xs) (y::ys));;

(编辑:我太晚了)

因此,在最坏的情况下,O(nm)中的代码是最好的.然而,IIUIC它总是执行n*m次操作,这不是最佳的.

我的方法是

1)写一个函数

group:'list - >('a*int)列表

计算相同元素的数量:

组[1,1,1,1,1,2,2,3] == [(1,5);(2,2);(3,1)]

2)使用它来使用与之前类似的代码合并两个列表(您可以将这些系数相乘)

3)写一个函数

取消组合:('a*int)列表 - >'列表

并撰写这三个.

这具有复杂度O(n + m + x),其中x是结果列表的长度.这是最好的恒定.

编辑:你走了:

let group x =
  let rec group2 l m =
    match l with
    | [] -> []
    | a1::a2::r when a1 == a2 -> group2 (a2::r) (m+1)
    | x::r -> (x, m+1)::(group2 r 0)
  in group2 x 0;;

let rec merge a b = match (a,b) with
   ([], xs) -> []
|  (xs, []) -> []
|  ((x, xm)::xs, (y, ym)::ys) -> if x == y then (x, xm*ym)::(merge xs ys)
                           else  if x <  y then merge xs ((y, ym)::ys)
                                           else merge ((x, xm)::xs) ys;;

let rec ungroup a =
  match a with
    [] -> []
  | (x, 0)::l -> ungroup l
  | (x, m)::l -> x::(ungroup ((x,m-1)::l));;

let crossjoin x y = ungroup (merge (group x) (group y));;



# crossjoin [2; 4; 6; 8; 8; 10; 12] [-7; -8; 2; 2; 3; 4; 4; 8; 8; 8;];;
- : int list = [2; 2; 4; 4; 8; 8; 8; 8; 8; 8]