列表交集算法实现只使用python列表（未设置）

Question

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

1. 迭代通过L1
2. 迭代通过L2
3. 如果元件是在L1和L2
4. 其添加到L
6. 迭代至L
从L1和L2中删除它
7. 将元素添加回L1和L2

我100％确定这不是Mathematica中用于评估列表交集的算法，但我无法真正想出更有效的方法。我不想在这个过程中修改L1和L2，因此我将这个交点加回到两个列表中。有任何想法吗？我不想使用列表以外的任何内置函数/数据类型，所以没有导入集或类似的东西。就我而言，这是一个算法和实现练习，而不是编程练习。

Answer 1

如何：

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中是否有重复都没有关系。

Answer 2

编辑：我读了错误的标题，并浏览了builtins部分。无论如何，我会把它留在这里，可能会帮助别人。

您可以使用set类型获得此结果。

>>> a = [1,2,3,4] 
>>> b = [3,4,5,6] 
>>> c = list(set(a) & set(b)) 
>>> c 
[3, 4] 

Answer 3

1. 创建一个临时表。
2. 迭代两个列表中的一个。哪一个并不重要。
3. 对于每一个元素，检查，看看是否在其他列表（if element in list2）存在元素，是不是已经在你的临时列表（相同的语法）
4. 如果这两个条件都为真，将其附加到您的临时列表。

---

我觉得不好张贴的解决方案，但它的诚实比我的文字更容易阅读：

def intersection(l1, l2): 
    temp = [] 

    for item in l1: 
     if item in l2 and item not in temp: 
      temp.append(item) 

    return temp 

Answer 4

凡是遍历L1，通过所有的每次L2迭代，将采取二次时间。唯一的改进方法是避免遍历所有L2。 （有一个类似的问题在最后去除L重复。）

如果您使用L2（和L）一set，当然每个in 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日志N），其中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 5

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

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