什么是将分类列表与丢失键的随身携带机制合并的最有效算法？ 我与多个有序列表一起工作，每个列表包含表单的元素（键，值），其中每个列表按钥匙按升序排序。我想将这些列表合并到一个单一的列表中...

Question

key

以下行为：

对于所有密钥联合中存在的每个密钥，输出元组应包含每个列表中的“当前”值。

如果输入列表在该密钥上没有条目，则应从该列表中启动最新值（即，使用小于或等于当前密钥的最新密钥中的值）。 这里是一个完整而最小的例子： 给定两个列表：

(key, value_from_list1, value_from_list2, ..., value_from_listK)

• 所需的输出为：

• A = [(1, a1), (2, a2), (10, a3)]
  B = [(1, b1), (8, b2), (10, b3)]

这种合并行为也应扩展到两个以上的列表（例如，将5个列表合并到具有6个元素的元素中，其中第一个元素是密钥）。 我的问题：

Algorithm效率：

将分类列表与丢失键的随身携带机制合并的最有效算法是什么？

我当前的解决方案是使用带有多个指针的清扫线算法（对于每个列表）来跟踪我通过键联合迭代的最新价值。如果我没记错的话，这将在o（n log（n））

中运行

Edit2025-03-13

Pseudocode

I’根据thisPost中的用户Smylic的建议创建了伪代码。正如他所说：

如果您需要输出k 每个键的值，最有效的算法采用θ（k·u） 时间，你 是唯一键的数量。

1. C = [
     (1, a1, b1),  // At key 1, both lists provide values.
     (2, a2, b1),  // At key 2, list A updates to a2; list B still uses b1.
     (8, a2, b2),  // At key 8, list B updates to b2; list A remains at a2.
     (10, a3, b3)  // At key 10, both lists update.
   ]

如果有不同的键和

function mergeLists(lists):
    k = number of lists
    pointers = array of size k, all initialized to 0
    lastValues = array of size k, initially set to None (or some default)
    output = empty list

    while true:
        minKey = None

        // Find the minimum key among the current pointers in all lists.
        for i from 0 to k-1:
            if pointers[i] < length(lists[i]):
                currentKey = lists[i][pointers[i]].key
                if minKey is None or currentKey < minKey:
                    minKey = currentKey

        // If no minimum key was found, all lists are exhausted.
        if minKey is None:
            break

        // Update lastValues for each list that has the current minKey
        for i from 0 to k-1:
            if pointers[i] < length(lists[i]) and lists[i][pointers[i]].key == minKey:
                lastValues[i] = lists[i][pointers[i]].value
                pointers[i] = pointers[i] + 1

        // Append the merged tuple (minKey, lastValues[0], lastValues[1], ..., lastValues[k-1])
        output.append( (minKey, lastValues[0], lastValues[1], ..., lastValues[k-1]) )

    return output

列表，则总输出为

n

。因此，您不能比这更快。您当前的算法已经是这样的速度，因此您可以改进的最大算法是一个恒定的因素。 当大多数键在大多数列表中都没有出现时，可以找到改进。但是，如果大多数键出现在大多数列表中，它将增加一个额外的因素。

因此，您的算法对我来说似乎足够好。