对python列表的子集进行排序,使其具有与其他列表中相同的相对顺序

Question

所以有一个列表说b = [b1, b2, b3]我希望能够以a这样的方式对列表进行排序,即所有bi存在的列表具有与之a相同的相对顺序b- 仅剩下其余a的元素.所以

a = [ b1, x, b3, y, b2] -> [ b1, x, b2, y, b3]
a = [ b1, x, b2, y, b3] -> no change
a = [ b1, x, y, b2]     -> no change
a = [ b3, x, b1, y, b2] -> [ b1, x, b2, y, b3]

b当然可以是元组或任何其他有序结构.我想出了什么

bslots = dict((x, a.index(x)) for x in a if x in b)
bslotsSorted = sorted(bslots.keys(), key=lambda y: b.index(y))
indexes = sorted(bslots.values())
for x,y in zip(bslotsSorted, indexes):
  a[y] = x

笨拙而且O(n ^ 2)

Answer 1

• 首先使用b键是项目的值创建一个字典,值是它的索引,我们将在a稍后使用它来对匹配的项目进行排序.

• 现在过滤出a该dict中存在的项目,dict提供O(1)查找.

• 现在对此筛选项列表进行排序并将其转换为迭代器.

• 现在a再次循环,并为每个项目检查dict中是否存在,然后从迭代器获取其值,否则按原样使用它.

def solve(a, b):
    dct = {x: i for i, x in enumerate(b)}
    items_in_a = [x for x in a if x in dct]
    items_in_a.sort(key=dct.get)
    it = iter(items_in_a)
    return [next(it) if x in dct else x for x in a]
...
>>> b = ['b1', 'b2', 'b3']
>>> a = [ 'b1', 'x', 'b3', 'y', 'b2']
>>> solve(a, b)
['b1', 'x', 'b2', 'y', 'b3']
>>> a = [ 'b1', 'x', 'b2', 'y', 'b3']
>>> solve(a, b)
['b1', 'x', 'b2', 'y', 'b3']
>>> a = [ 'b1', 'x', 'y', 'b2']
>>> solve(a, b)
['b1', 'x', 'y', 'b2']
>>> a = [ 'b3', 'x', 'b1', 'y', 'b2']
>>> solve(a, b)
['b1', 'x', 'b2', 'y', 'b3']

整体时间复杂度最大化(O(len(a)), O(len(b)), O(items_in_a_length log items_in_a_length).