仅使用python列表（而不是集合）实现列表交集算法

Question

我要用python的交集写下重复的列表。我是python和编程的新手，所以如果这听起来效率低下，请原谅我，但我无法想出其他任何东西。这里，L1和L2是有问题的两个列表，L是交集。在

1. 迭代L1
2. 迭代L2
3. 如果元素在L1和L2中
4. 把它加到L上
5. 将其从L1和L2移除
6. 迭代L
7. 将元素添加回L1和L2

我百分之百地肯定这不是Mathematica中用来计算列表交集的算法，但我真的无法想出更有效的方法。我不想在这个过程中修改L1和L2，因此我将交集添加回两个列表中。有什么想法吗？我不想使用除了列表之外的任何内置函数/数据类型，所以没有导入集之类的东西。就我而言，这是一个算法和实现练习，而不是编程练习。在

Answer 1

这里有一个更快的解决方案：

def intersect_sorted(a1, a2):
  """Yields the intersection of sorted lists a1 and a2, without deduplication.

  Execution time is O(min(lo + hi, lo * log(hi))), where lo == min(len(a1),
  len(a2)) and hi == max(len(a1), len(a2)). It can be faster depending on
  the data.
  """
  import bisect, math
  s1, s2 = len(a1), len(a2)
  i1 = i2 = 0
  if s1 and s1 + s2 > min(s1, s2) * math.log(max(s1, s2)) * 1.4426950408889634:
    bi = bisect.bisect_left
    while i1 < s1 and i2 < s2:
      v1, v2 = a1[i1], a2[i2]
      if v1 == v2:
        yield v1
        i1 += 1
        i2 += 1
      elif v1 < v2:
        i1 = bi(a1, v2, i1)
      else:
        i2 = bi(a2, v1, i2)
  else:  # The linear solution is faster.
    while i1 < s1 and i2 < s2:
      v1, v2 = a1[i1], a2[i2]
      if v1 == v2:
        yield v1
        i1 += 1
        i2 += 1
      elif v1 < v2:
        i1 += 1
      else:
        i2 += 1

它在O(min(n + m, n * log(m)))时间内运行，其中n是长度的最小值，m是最大值。它同时迭代两个列表，在开始时跳过尽可能多的元素。在

此处提供分析：http://ptspts.blogspot.ch/2015/11/how-to-compute-intersection-of-two.html

Answer 2

任何迭代L1，每次迭代所有L2的操作都需要二次时间。改进的唯一方法是避免遍历所有L2。（在末尾从L中删除重复项也有类似的问题。）

如果使用set表示L2（和L），当然每个in L2步都是恒定时间，因此整个算法是线性的。而且您可以始终构建自己的哈希表实现，而不是使用set。但这是一个很大的工作。在

使用二叉搜索树，甚至只使用排序列表和binary_find函数，您可以在O（nlogn）中完成。而且这binary_find更容易自己编写。所以：

S2 = sorted(L2)
L = [element for element in L1 if binary_find(element, S2)]
S = remove_adjacent(sorted(L))

或者，更简单地说，也可以对L1排序，然后就不需要remove_adjacent：

^{pr2}$

不管怎样，这是O（nlogn），其中N是较长列表的长度。相比之下，原始答案是O（N^2），其他答案是O（N^3）。当然有点复杂，但还是很容易理解的。在

您需要编写binary_find（如果适用的话，remove_adjacent），因为我假设如果您甚至不想使用额外的内置函数，您就不想使用stdlib之外的东西。但那真的很简单。例如：

def binary_find(element, seq):
    low, high = 0, len(seq), 
    while low != high:
        mid = (low + high) // 2
        if seq[mid] == element:
            return True
        elif seq[mid] < element:
            low = mid+1
        else:
            high = mid
    return False

def remove_adjacent(seq):
    ret = []
    last = object()
    for element in seq:
        if element != last:
            ret.append(element)
        last = element
    return ret

如果您甚至不想使用sorted或list.sort，那么您也可以很容易地编写自己的排序。在

Answer 3

怎么样：

1. 遍历L1
2. 迭代L2
3. 如果（在L1和L2中）而不是在L中->；添加到L

不是特别有效，但是在代码中它看起来像这样（通过重复来说明这一点）：

>>> L1 = [1,2,3,3,4]
>>> L2 = [2,3,4,4,5]
>>> L = list()
>>> for v1 in L1:
        for v2 in L2:
            if v1 == v2 and v1 not in L:
                L.append(v1)
>>> L
[2,3,4]

只需检查元素是否已在L中，如果不在L中则添加到L中，就可以避免从L1和L2中删除。那么在L1和L2中是否有重复并不重要。在