仅使用Python列表（非集合）的列表交集算法实现

-1 投票

6 回答

3016 浏览

提问于 2025-04-17 15:41

我一直在尝试用Python写一个处理列表交集的算法，特别是要考虑重复的情况。我对Python和编程还是个新手，所以如果这个方法听起来不够高效，请多包涵。不过我想不出其他更好的办法。这里，L1和L2是我们要处理的两个列表，而L是交集的结果。

先遍历L1这个列表
然后遍历L2这个列表
如果某个元素同时在L1和L2里
就把这个元素加到L中
然后把这个元素从L1和L2中删除
接着遍历L
把元素再加回到L1和L2中

我百分之百确定这不是Mathematica用来计算列表交集的算法，但我真的想不出更高效的办法。我不想在这个过程中修改L1和L2，所以才会把交集的结果再加回去。我不想使用任何内置的函数或数据类型，除了列表，所以不想导入集合之类的东西。对我来说，这只是一个算法和实现的练习，而不是编程的练习。

数据结构效率优化编程练习算法实现结果处理遍历重复元素列表交集

6 个回答

任何对 L1 进行遍历的操作，如果每次都要遍历整个 L2，那么这个过程的时间复杂度是平方级别的。要想提高效率，最好的办法就是避免每次都遍历整个 L2。（在最后去除 L 中的重复项时也会遇到类似的问题。）

如果你用 set 来处理 L2（还有 L），那么每次检查 L2 中是否存在某个元素的时间都是固定的，这样整体算法的时间复杂度就变成线性级别了。而且你也可以自己实现一个哈希表，而不是使用 set，不过那样会比较麻烦。

如果使用二叉搜索树，或者仅仅是一个排序好的列表加上一个 binary_find 函数，你就可以把时间复杂度降低到 O(N log N)。而且自己写这个 binary_find 也相对简单。所以：

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

或者，更简单的方法是把 L1 也排序，这样你就不需要 remove_adjacent 了：

S1, S2 = sorted(L1), sorted(L2)
L = []
for element in S1:
    if binary_find(element, S2) and (not L or L[-1] != element):
        L.append(element)

无论哪种方式，时间复杂度都是 O(N log N)，其中 N 是较长列表的长度。相比之下，最初的方法是 O(N^2)，而其他答案则是 O(N^3)。当然，这样会稍微复杂一点，但其实还是挺容易理解的。

你需要自己写 binary_find（如果需要的话，还要写 remove_adjacent），因为我假设你不想使用标准库中的东西，甚至连额外的内置函数都不想用。不过这真的很简单。例如：

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 都不想用，你也可以很容易地自己写一个排序函数。

回答于 2025-04-17 由 Python大师

分享举报

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

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

回答于 2025-04-17 由 Python大师

分享举报

这样做怎么样：

遍历L1这个列表
遍历L2这个列表
如果某个元素同时在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里来避免从L1和L2中删除元素，如果不在就加到L里。这样的话，L1和L2中有重复的元素也没关系。

回答于 2025-04-17 由 Python大师

分享举报

仅使用Python列表（非集合）的列表交集算法实现

6 个回答

撰写回答