如何高效统计列表A中早于列表B同元素出现的元素数量？

问题分析 #

需求是统计列表A中满足元素在A的位置早于其在列表B中对应位置的元素数量。例如A=[2,3,4,1]、B=[1,2,3,4]时，元素2、3、4符合条件，返回3。

原代码的性能瓶颈 #

原代码中a[i] not in b[:i]的操作存在两个低效点：每次切片b[:i]会生成新列表，且in判断是线性扫描，整体时间复杂度为O(n²)，处理大规模数据时会非常缓慢。

优化思路 #

1. 预处理列表B：用字典存储每个元素在B中的索引位置，后续查找元素位置的时间复杂度可降至O(1)。
2. 遍历列表A：对每个元素，直接对比其在A的索引和在B中的索引，若A的索引更小则计数。

优化后的代码 #

def count(a, b):
    # 预处理B，记录每个元素的位置（假设元素唯一，若有重复可按需调整为第一个/最后一个位置）
    b_pos = {val: idx for idx, val in enumerate(b)}
    count = 0
    for idx, val in enumerate(a):
        # 若A包含B中没有的元素，可根据需求决定是否跳过
        if val in b_pos and idx < b_pos[val]:
            count += 1
    return count

性能说明 #

• 预处理B的时间复杂度为O(n)，遍历A的时间复杂度为O(n)，总时间复杂度为O(n)，相比原代码的O(n²)，处理大规模列表时性能提升显著。
• 若B中存在重复元素，可修改字典构建逻辑，比如存储元素的所有位置，再判断是否存在某个位置大于当前A的索引。

内容的提问来源于stack exchange，提问作者Iltsukka