本文介绍一种针对固定列表的多次查询优化方案：通过预构建索引字典，将单次“x是否出现在y之前”的查询时间从o(n)降至平均o(1)，适用于元素可能重复、且需高频查询的场景。
本文介绍一种针对固定列表的多次查询优化方案：通过预构建索引字典，将单次“x是否出现在y之前”的查询时间从o(n)降至平均o(1)，适用于元素可能重复、且需高频查询的场景。
在实际开发中，我们常需判断某个元素是否位于另一元素之前——例如解析配置顺序、验证依赖关系或处理事件日志。若仅执行一次查询，遍历列表直到遇到 x 或 y 即可（时间复杂度 O(n)）；但当同一列表 L 需响应数百甚至上千次不同 (x, y) 对的查询时，重复遍历将显著拖慢性能。
此时，预计算 + 哈希索引是更优解。核心思想是：为列表 L 构建两个查找表：
- first_occurrence：记录每个元素首次出现的索引；
- last_occurrence：记录每个元素最后一次出现的索引。
这样，对于任意查询 “x 是否出现在 y 之前”，只需判断 first_occurrence[x] < last_occurrence[y] —— 因为只要 x 的最早位置早于 y 的最晚位置，就必然存在某对 (x_i, y_j) 满足 i < j，即 x 出现在 y 之前（注意：题目仅要求“x 出现在 y 之前”，不要求相邻或唯一，因此该逻辑完备）。
以下是完整实现示例：
def build_position_index(lst):
first = {}
last = {}
for idx, elem in enumerate(lst):
if elem not in first:
first[elem] = idx
last[elem] = idx
return first, last
# 示例使用
L = ["n", "s", "t", "r", "i", "n", "g", "r"]
first_occurrence, last_occurrence = build_position_index(L)
# 查询：'n' 是否出现在 'r' 之前？
x, y = "n", "r"
result = first_occurrence[x] < last_occurrence[y] # True（0 < 7）
print(result) # True
# 查询：'r' 是否出现在 'n' 之前？
x, y = "r", "n"
result = first_occurrence[x] < last_occurrence[y] # True（3 < 5）
print(result) # True（因首个 'r' 在索引3，最后一个 'n' 在索引5）⚠️ 注意事项：
- 该方法不依赖元素唯一性，天然支持重复元素；
- 预构建时间复杂度为 O(n)，空间复杂度 O(k)，k 为去重后元素个数；
- 单次查询为两次哈希表查找，平均时间复杂度 O(1)；
- 若业务语义要求“任意 x 都在任意 y 之前”（即所有 x 的位置均小于所有 y 的位置），则应使用 max_first[x] < min_last[y]，此时需额外维护 min_last（即 y 的首次出现）和 max_first（即 x 的末次出现），但本题标准解读采用更宽松且高效的 first[x] < last[y]；
- 字典键必须是可哈希类型（如 str、int、tuple 等），不可用 list 或 dict 作为 x/y。
综上，面对静态列表的高频相对位置查询，预建双索引字典是兼顾简洁性、通用性与性能的工程优选方案。
