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

A 和 B 不相交。是不是我事先不知道 A/B 中元素的数量和它们的值。我想比较列表和删除元素中元素的值：

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]，反之亦然。

4

4 回答 4

1

在你编辑之前我想出了这个。但似乎输出不是您所期望的。无论如何，它可能会帮助您走上正轨：

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这里不是您所期望的。我会努力改进这一点。

于 2012-07-18T08:16:29.950 回答
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
于 2012-07-18T08:25:22.550 回答
0

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

>>> 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。

于 2012-07-18T10:14:13.337 回答
0

所以，如果我没看错，你的例子中期望的输出是 [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。

于 2012-07-18T14:30:38.297 回答