两个列表的比较元素

Question

A = [a1, a2, a3...] #a1<a2<a3... 
B = [b1, b2...] #b1<b2<b3... 

A和B不相交。我是否预先知道A/B中元素的数量和它们的价值？我想比较这两个列表中的元素的值并删除IFF元素：

delete a[i+1] if there is no b[j] such that a[i]<b[j]<a[i+1] 
delete b[i+1] if there is no a[j] such that b[i]<a[j]<b[i+1] 

最后，我要分开列表，而不是A的组合B.

例如，如果A[0] < B[0]，A = [1,10,40]，B = [15,30]。首先比较A[1]和B[0]。删除10，因为B中没有元素在1到15之间。 然后删除15，因为没有元素存在了，因此15和30.输出应该是：如果您尝试排序新的2列表的元素，它应该是A[0]<B[0]<A[1]<B[1]<...

如果是A[0] > B[0]，反之亦然。

Answer 1

a = [1, 10, 40] 
b = [15, 30] 

srcs = [a, b] 
dsts = [[], []] 
prev_which = -1 
while all(srcs): 
    which = int(srcs[0][0] > srcs[1][0]) 
    elem = srcs[which].pop(0) 
    if prev_which != which: 
     dsts[which].append(elem) 
    prev_which = which 
for src, dst in zip(srcs,dsts): 
    if src: 
     dst.append(src.pop(0)) 
a, b = dsts 

回报：

a = [1, 40] 
b = [15] 

和

a = [3, 4, 6, 7, 8, 9] 
b = [1, 2, 5, 10] 

返回[3, 6]和[1, 5, 10]。

编辑：另一种可能性：

import itertools as it 
import operator as op 

a = [3, 4, 6, 7, 8, 9] 
b = [1, 2, 5, 10] 
srcs = [a, b] 
dsts = [[], []] 

for which, elems in it.groupby(sorted((x, i) for i in (0,1) for x in srcs[i]), key=op.itemgetter(1)): 
    dsts[which].append(next(elems)[0]) 
a, b = dsts 

Answer 2

我在编辑之前想出了这个。但看起来输出结果并不符合你的期望。总之，它可以帮助你在正确的轨道上：

a = range(0, 30, 3) 
b = range(0, 20, 2) 

a.sort() 
b.sort() 

A = [a[i+1] for i in range(len(a)-1) if any(a[i]<b[j]<a[i+1] for j in range(len(b)-1))] 
B = [b[i+1] for i in range(len(b)-1) if any(b[i]<a[j]<b[i+1] for j in range(len(a)-1))] 

result = sorted(A+B) 

print a, b 
print result 

这是“字面意思是”你所表达的，但这里的result是不是你所期望的。我会尽力改善这一点。

Answer 3

使用对开模块可能是一个很好的解决方案，我知道：

>>> def sort_relative(L1, L2): 
    # Switch if needed 
    if L1[0] > L2[0]: 
     L1, L2 = L2, L1 
    i = 0 
    while i + 1 < max(len(L1), len(L2)): 
     try: 
      # We know that L1[i] < L2[i] 
      # Get indexes where L2[i] and L2[i + 1] should be inserted 
      i11 = bisect.bisect_left(L1, L2[i]) 
      i12 = bisect.bisect_left(L1, L2[i + 1]) 

      # This condition allows to know if one element of L1 
      # was found between L2[i] and L2[i + 1]: 
      # - if so, we have L1[i] < L2[i] < L1[i + 1] < L2[i + 1] 
      # - else we have L1[i] < L2[i] < L1[i + 1] but 
      # we don't know between L1[i + 1] and L2[i + 1] 
      if L1[i11] < L2[i + 1]: 
       L1 = L1[:i + 1] + [L1[i11]] + L1[i12:] 
       index1, index2 = i + 1, i + 2 
      else: 
       L1 = L1[:i + 1] + L1[i12:] 
       index1, index2 = i, i + 1 

      # Do the same kind of symetric search, 
      # with indexes computed above 
      i21 = bisect.bisect_left(L2, L1[index1]) 
      i22 = bisect.bisect_left(L2, L1[index2]) 
      if L2[i21] < L1[index2]: 
       L2 = L2[:index1] + [L2[i21]] + L2[i22:] 
      else: 
       L2 = L2[:index1] + L2[i22:] 
     # Little trick not to test indexes everywhere: 
     # lists are browsed at the same time 
     except IndexError: 
      pass 

     # Next index ! 
     i += 1 

    # Show result 
    print 'L1:', L1, '- L2:', L2 


>>> sort_relative([1, 10, 50], [15, 30]) 
L1: [1, 50] - L2: [15] 
>>> sort_relative([17, 18, 50], [15, 30]) 
L1: [15, 30] - L2: [17, 50] 
>>> sort_relative([1, 10, 12, 25, 27, 50], [15, 30, 70]) 
L1: [1, 25, 50] - L2: [15, 30, 70] 
>>> sort_relative([1, 10, 12, 25, 27, 50], [15, 30, 34, 70]) 
L1: [1, 25, 50] - L2: [15, 30, 70] 
>>> 

当一个数字是我没有考虑到的情况下都在A和B。

Answer 4

所以，如果我正确阅读，你的例子所需的输出是[1,40]和[15]，是吗？

如果是这样，以下将得到正确的结果，但我确信有一个更紧密的方式来做到这一点。

a = [1, 10, 40] 
b = [15, 30] 
c = sorted([[e_a,'a'] for e_a in a] + [[e_b,'b'] for e_b in b]) 
indices = [] 

for i in range(len(c)-1): 
    if c[i][1] == c[i+1][1]: 
     indices.append(i+1) 

for e in sorted(indices, reverse=True): 
    del c[e] 

a,b = [e[0] for e in c if e[1]=='a'],[e[0] for e in c if e[1]=='b'] 

首先 - 合并列表并对它们进行排序，同时记录它们来自哪个列表。

第二个 - 然后删除合并列表中下一个项目来自同一个源列表的所有实例。

第三 - 更新a和b。