algorithm - 将两个列表合并为一个保持顺序且没有重复元素的列表

Question

我有两个列表，我想将它们合并在一起。假设它们为 list_left 和 list_right 合并规则为:

1. 两个列表没有重复元素，合并后的结果列表也没有重复元素。
2. 合并中元素的顺序必须与 list_left 和 list_right 中的顺序相同。
3. 如果两个元素(e1、e2)同时出现在 list_left 和 list_right 中，并且它们在 list_left 和 list_right 中是不同的。它必须保持 list_right 中的顺序。换句话说，如果 list_right 中 e1 位于 e2 之前，则 e1 必须位于 e2 之前code> 在合并列表中，无论它们在 list_left 中如何。
4. 如果某些元素未在上述三个规则中提及，它们可以出现在结果合并列表中的任何位置。

一些示例:

list_left:   w  h  i  j  k 
list_right:  a  w  t  i  n
merged:      a  w  h  t  i  j  k  n


list_left:   w  h  i  j  k 
list_right:  j  w  m  n  a
merged:      j  w  h  i  k  m  n  a


list_left:   j  w  m  n  a
list_right:  w  h  i  j  k 
merged:      w  h  i  j  m  n  a  k


list_left:   a  b  c  d 
list_right:  e  f  g  h
merged:      a  b  c  d  e  f  g  h

有什么方法可以解决这个问题吗？

Answer 1

只需复制 list_left 中尚未出现在 list_merged 中的元素即可。但是，当您在 list_left 中看到 list_right 中的元素而不是 list_merged 中的元素时，请从 list_right 向上复制元素到这个元素。完成 list_left 后，复制 list_right 中剩余的内容:

list_left = "whijk"
list_right = "jwmna"
list_merged = ""
pos = 0

for x in list_left:
  if not x in list_merged:
    if x in list_right:
      xpos = list_right.index(x)
      list_merged += list_right[pos:xpos]
      pos = xpos + 1
    list_merged += x
list_merged += list_right[pos:]

print list_merged

为了提高性能，您可以创建一对集合，并用这些集合中的搜索替换列表中的搜索。