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

Question

我有两个这样的字符串列表（两个列表具有相同的项目但顺序不同）：

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

要lst2基于 进行排序lst1，我想lst2在lst1. 对于重复项，我想采用尚未采用的最小索引。

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

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]