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

当保证一个元素在 L ,您可以使用一个简单的字典,将每个元素映射到其索引。然而,当一个元素可以出现多次时,它需要两个字典,一个用于存储元素的第一次出现,另一个用于保存元素的最后一次出现。

L = ["n", "s", "t", "r", "i", "n", "g", "r"]
elem2index_first = {}
elem2index_last = {}

for index, elem in enumerate(L):
    if elem not in elem2index_first:  # Only update on the first occurrence
        elem2index_first[elem] = index
    elem2index_last[elem] = index  # Overwrite on whatever the previous index was

然后,它需要 an average of a constant time complexity 对于每个查询,因为它只需要两次字典查找。

print(elem2index_first[x] < elem2index_last[y])  # x comes before y

就像上面建议的答案一样,您可以使用两个索引映射并进行查找。

xs = ["p", "x", "k", "j", "p", "y", "x", "l"]

n = len(xs)
last_seen = dict(zip(xs, range(n)))
first_seen = dict(zip(reversed(xs), range(n - 1, -1, -1)))

is_x_before_y = first_seen['x'] < last_seen['y']
assert is_x_before_y

def ensure_x_bfr_y(L, xy):
    
    #Declare empty dict
    dct = {}
    
    # Iterate thru xy
    for x in xy:
    
        #Find the index of x and y in L
        x_idx = L.index(x[0])
        y_idx = L.index(x[1])
        
        #If the index of x is lesser than y make key of dict as x and value as y. Else false
        if x_idx < y_idx:
            dct[x] = True
        else:
            dct[x] = False
    return dct

L = [23, 44, 11, 89, 65, 40, 71, 84]
xy = (23, 71), (89, 84), (40, 23), (65, 11)
r = ensure_x_bfr_y(L,xy)
print(r) # Output: {(23, 71): True, (89, 84): True, (40, 23): False, (65, 11): False}