当需对同一列表反复执行“x 是否在 y 之前出现”的查询时，预构建首/末次出现索引字典可将单次查询降至平均 o(1) 时间复杂度，显著优于每次遍历的 o(n) 方法。
当需对同一列表反复执行“x 是否在 y 之前出现”的查询时，预构建首/末次出现索引字典可将单次查询降至平均 o(1) 时间复杂度，显著优于每次遍历的 o(n) 方法。
在 Python 中，若仅需判断两个确定存在于列表中的元素 x 和 y 的相对顺序（即 x 的首次出现位置是否严格小于 y 的末次出现位置），最高效的策略是预处理一次列表，构建索引映射结构，而非对每个查询都线性扫描。
核心思想是：
- 若 x 的第一次出现位置 < y 的最后一次出现位置，则必然存在某个 x 出现在某个 y 之前 → 判定为 True；
- 反之，若 x 的首次位置 ≥ y 的末次位置，则所有 x 都在所有 y 之后（或重叠但无前置关系）→ 判定为 False。
该逻辑覆盖了元素重复出现的通用场景，且语义严谨：只要存在一对 (x_i, y_j) 满足 i < j，即认为 “x 出现在 y 之前”。
实现上，使用两个字典完成 O(n) 预处理：
L = ["n", "s", "t", "r", "i", "n", "g", "r"]
elem2first = {} # 元素 → 首次索引
elem2last = {} # 元素 → 末次索引
for idx, elem in enumerate(L):
if elem not in elem2first:
elem2first[elem] = idx
elem2last[elem] = idx # 每次更新，最终保留最大索引此后，任意查询均可在平均 O(1) 时间内完成：
def x_before_y(x, y):
return elem2first[x] < elem2last[y]
# 示例
print(x_before_y("n", "r")) # True: 第一个 'n' 在索引 0，最后一个 'r' 在索引 7
print(x_before_y("r", "n")) # True: 第一个 'r' 在索引 3，最后一个 'n' 在索引 5 → 3 < 5
print(x_before_y("g", "s")) # False: 第一个 'g' 在索引 6，最后一个 's' 在索引 1 → 6 < 1 为假⚠️ 注意事项：
- 此方法依赖前提：x 和 y 均保证在 L 中至少出现一次（如题设），否则字典查找会抛出 KeyError；生产环境建议增加 in 检查或使用 dict.get() 提供默认值；
- 若业务语义要求“任意 x 都在任意 y 之前”（即 max_index(x) < min_index(y)），则需额外维护 elem2min 和 elem2max，但本方案的 first < last 已满足最常见的“存在性前置”需求；
- 空间复杂度为 O(k)，其中 k 是列表中不同元素个数，通常远小于列表长度 n，性价比极高。
综上，通过一次 O(n) 预处理构建双字典索引，可将高频查询降维至常数级，是兼顾简洁性、鲁棒性与性能的推荐解法。
