如何 Return 在 Python 中合并 3 个排序数组后的步骤

Question

我只想合并 Python 中的 3 个排序数组，但不想要值，只想要像从哪里获得值那样的步骤

让我们说这是 3 个排序数组

A = [1,3,4,6]
B = [2,3,4,5]
C = [1,5,9]

原来的合并排序是

Sorted = [1,1,2,3,3,4,4,5,5,6,9]

但我想要的不是这个，而是我们从哪个数组中获得的值

Sorted = [A,C,B,A,B,A,B,B,C,A,C]

你可以说我想要的是我们首先从哪个数组得到的步骤等等那么请指导我如何在 Python?

上做到这一点

Answer 1

一种方法：

from heapq import merge
from operator import itemgetter

A = [1, 3, 4, 6]
B = [2, 3, 4, 5]
C = [1, 5, 9]

lst = [[(val, label)for val in values] for label, values in zip(["A", "B", "C"], [A, B, C])]
res = [label for _, label in merge(*lst, key=itemgetter(0))]
print(res)

输出

['A', 'C', 'B', 'A', 'B', 'A', 'B', 'B', 'C', 'A', 'C']

首先，为每个输入列表创建一个元组列表，其中元组的第一个元素是值，第二个是指示来源的标签，这是在这一行中完成的：

lst = [[(val, label) for val in values] for label, values in zip(["A", "B", "C"], [A, B, C])]

之后使用heapq.merge合并列表，仅使用元组的第一个元素作为比较的键，然后提取标签：

res = [label for _, label in merge(*lst, key=itemgetter(0))]

上面的代码等价于下面的for循环：

res = []
merged = merge(*lst, key=itemgetter(0))
for _, label in merged:
    res.append(label)

如何 Return 在 Python 中合并 3 个排序数组后的步骤

How to Return The Steps After Merging 3 Sorted Arrays in Python

python

arrays

algorithm

mergesort