合并两个列表，同时删除重复项

Question

目标是合并（追加）两个列表，同时删除重复项。

let rec find_dup a lst =
  match lst with
    | [] -> false
    | hd::tl -> if (hd == a) then true else find_dup a tl;;

let rec app lst2 lst1 =
  match lst1 with
    | [] -> lst2
    | hd::tl -> if (find_dup hd lst2) then (app tl lst2)
     else hd::app tl lst2
     ;;

我的代码是这样的，但是当测试用例是

app [4;5;6;7] [1;2;3;4]

答案应该是

[1;2;3;4;5;6;7]

但我不断得到

 - : int list = [1; 2; 5; 3; 6; 4; 7]

发生什么事了？

Answer 1

您要为每个递归调用切换列表。

查看函数定义的参数顺序：

let rec app lst2 lst1

然后递归函数调用：

app tl lst2

另外，顺便提一下，

find_dup

已经存在于标准库中。这叫

List.mem

。

Answer 2

如果我们找出你的例子，我们就可以明白 glennsl 在说什么。

app [4; 5; 6; 7] [1; 2; 3; 4]
  find_dup 1 [4; 5; 6; 7] -> false
  1 :: app [2; 3; 4] [4; 5; 6; 7]
    find_up 4 [2; 3; 4] -> true
    1 :: app [5; 6; 7] [2; 3; 4]
      find_up 2 [5; 6; 7] -> false
      1 :: 2 :: app [3; 4] [5; 6; 7]
        find_up 5 [3; 4] -> false
        1 :: 2 :: 5 :: app [6; 7] [3; 4]
          find_up 3 [6; 7] -> false
          1 :: 2 :: 5 :: 3 :: app [4] [6; 7]
            find_up 6 [4] -> false
            1 :: 2 :: 5 :: 3 :: 6 :: app [7] [4]
              find_dup 4 [7] -> false
              1 :: 2 :: 5 :: 3 :: 6 :: 4 :: app [] [7]
                find_dup 7 [] -> false
                1 :: 2 :: 5 :: 3 :: 6 :: 4 :: 7 :: app [] []
                  [1; 2; 5; 3; 6; 4; 7]

如果我们摆脱列表的反转：

let rec find_dup a lst =
  match lst with
  | [] -> false
  | hd::tl -> hd = a || find_dup a tl

let rec app lst1 lst2 =
  match lst1 with
  | [] -> lst2
  | hd::tl -> 
      if find_dup hd lst2 then app tl lst2
      else hd :: app tl lst2

现在：

app [4; 5; 6; 7] [1; 2; 3; 4]
  find_dup 4 [1; 2; 3; 4] -> true
  app [5; 6; 7] [1; 2; 3; 4]
    find_dup 5 [1; 2; 3; 4] -> false
    5 :: app [6; 7] [1; 2; 3; 4]
      find_dup 6 [1; 2; 3; 4] -> false
      5 :: 6 :: app [7] [1; 2; 3; 4]
        find_dup 7 [1; 2; 3; 4]
        5 :: 6 :: 7 :: app [] [1; 2; 3; 4]
          5 :: 6 :: 5 :: [1; 2; 3; 4]
          [5; 6; 7; 1; 2; 3; 4]

当然，这是低效的，因为我们在循环 (

find_dup

) 中有一个循环 (

app

)，这意味着这具有二次运行时复杂性。我们可以做得更好。

让我们追加两个列表，然后对整个列表进行排序。我们会得到：

[1; 2; 3; 4; 4; 5; 6; 7]

排序的时间复杂度为 O(n * log n)，连接列表的时间复杂度为 O(n)。删除重复项是一个 O(n) 操作。

# let[@tail_mod_cons] rec uniq = function
    | ([] | [_]) as lst -> lst
    | a::(b::_ as tl) when a = b -> uniq tl
    | a :: tl -> a :: uniq tl;;
val uniq : 'a list -> 'a list = <fun>
# uniq [1; 2; 3; 4; 4; 5; 6; 7];;
- : int list = [1; 2; 3; 4; 5; 6; 7]