如何有效检查列表中 x 是否出现在 y 之前

给定Python中的列表 L ，以及保证位于 x 中的两个元素 y 和 L ，我想知道 x 是否出现在 y 中 L 之前。

如果只有一对，我可以简单地循环 L 直到找到 x 或 y 这所花费的时间与 L 的长度成线性关系。但是，我必须回答许多此类相同 L （不同 x 和 y ）的查询。有没有一种有效的方法，也许是Python中的数据结构或迭代器，我可以用它来快速回答许多相同的查询 L ？

可以通过预处理列表 L 来创建一个字典，将每个元素映射到它的索引，从而有效地检查列表中 x 是否出现在 y 之前。然后，可以使用该字典快速检查任何对 (x, y) 的索引。

以下是方法：

def check_order(L, pairs):
    """
    检查列表 L 中多个对中 x 是否出现在 y 之前。

    Args:
        L: 包含元素的列表。
        pairs: (x, y) 对的列表，其中 x 和 y 是 L 中的元素。

    Returns:
        一个布尔值列表，对应于每个对的结果。 
    """

    # 创建一个字典，将每个元素映射到它的索引
    element_indices = {element: index for index, element in enumerate(L)}

    # 检查每个对
    results = []
    for x, y in pairs:
        if element_indices[x] < element_indices[y]:
            results.append(True)
        else:
            results.append(False)

    return results

# 示例用法
L = [1, 2, 3, 4, 5]
pairs = [(1, 3), (4, 2), (3, 5)]

results = check_order(L, pairs)
print(results)  # 输出：[True, False, True]

说明：

1. 预处理：
2. 我们创建一个名为 element_indices 的字典。

3. 我们遍历列表 L ，并将每个 element 及其 index 存储在字典中。这样可以让我们稍后通过其索引高效地检索元素。

4. 检查对：

5. 我们遍历 pairs 列表中的每个对 (x, y)。
6. 对于每个对，我们使用字典 element_indices 检索 x 和 y 的索引。

7. 如果 x 的索引小于 y 的索引，则表示 x 在 L 中出现在 y 之前，我们将 True 追加到 results 列表中。否则，我们将 False 追加到列表中。

8. 返回值：

9. 函数 check_order 返回一个布尔值列表 results ，其中每个值对应于输入 pairs 列表中相应对的结果。

时间复杂度：

• 预处理步骤的时间复杂度为 O(n)，其中 n 是 L 的长度。
• 检查对步骤的时间复杂度为 O(m)，其中 m 是对的数量。

空间复杂度：

• 字典 element_indices 的空间复杂度为 O(n)。

通过预处理列表 L ，我们只需要对每个对执行一次恒定时间的查找操作，从而使其更有效率。这种方法在需要针对同一个列表执行多个查询时特别有用。