对python列表的子集进行排序，使其具有与其他列表相同的相对顺序 [英] Sort a subset of a python list to have the same relative order as in other list

问题描述

所以有一个列表说 b = [b1，b2，b3] 我希望能够对列表 a 的方式使得 a 中也存在的所有 bi 具有相对于 b -仅剩下 a 个元素的其余部分。因此

So having a list say b = [b1, b2, b3] I want to be able to sort a list a in such a way that all bi's that also exist in a have the same relative order as in b - leaving the rest of a's elements alone. So

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当然可以是元组或任何其他有序结构。我想出了什么

b of course may be a tuple or any other ordered structure. What I came up with

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）

is clumsy and O(n^2)

推荐答案




• 首先使用<$ c中的项创建字典$ c> b ，其中键是项目，值是它的索引，稍后我们将使用它对 a 中匹配的项目进行排序。

  • First create a dictionary using items from b where the key is the item and value is its index, we will use this to sort the matched items in a later on.

    现在从该dict中存在的 a 中过滤出项，dict提供O（1）查找。

    Now filter out item from a that are present in that dict, dict provides O(1) lookup.

    现在对已过滤项目列表进行排序，并将其转换为迭代器。

    Now sort this list of filtered items and convert it to an iterator.

    现在再次遍历 a ，对于每个项目检查dict中是否存在，然后从迭代器获取其值，否则按原样使用它。

    Now loop over a again and for each item check if is present in dict then fetch its value from iterator otherwise use it as is.

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

    这篇关于对python列表的子集进行排序，使其具有与其他列表相同的相对顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！