python - 根据具有相同项目但顺序不同的另一个列表对具有重复项的列表进行排序

Question

我有两个这样的字符串列表(两个列表有相同的项目，但顺序不同):

lst1 = ['C', 'H', 'H', 'H', 'C', 'O', 'O', 'H']
lst2 = ['H', 'H', 'C', 'O', 'H', 'O', 'H', 'C']

要根据 lst1 对 lst2 进行排序，我想为 lst1 中的每个项目找到 lst2 索引.对于重复项，我想采用尚未采用的最小索引。

我想知道获取这样一个索引列表的最快方法:

ids = [2, 0, 1, 4, 7, 3, 5, 6]

然后我可以通过

对 lst2 进行排序

newlst2 = [lst2[i] for i in ids]

由于有重复，获取列表索引的正常方式

ids = [lst2.index(x) for x in lst1]

会给出错误的结果

ids = [2, 0, 0, 0, 2, 3, 3, 0]

有什么建议吗？

Answer 1

您可以收集每个值的索引，然后使用这些集合。花费 O(n) 时间。

from collections import defaultdict, deque

indexes = defaultdict(deque)
for i, x in enumerate(lst2):
    indexes[x].append(i)

ids = [indexes[x].popleft() for x in lst1]