如何识别数组中相对位置变动的元素（更新场景）

问题核心 #

原数组arrA按元素最后更新时间排序，更新部分元素后得到新数组arrB：更新的元素会被移到arrB最前面，未更新元素保持arrA中的相对顺序不变。需要仅通过两个数组的顺序，识别出被更新的元素ID。

原有方法的问题 #

使用zip逐位对比数组的方法仅能发现相同位置的元素差异，无法识别“元素被更新后移到前面，但恰好出现在原位置”的情况（比如示例中的ID2），会导致错误结果。

正确解决方案 #

利用“未更新元素在arrB中的相对顺序与arrA完全一致”的规则，通过从后往前遍历找到未更新元素的起始位置，从而分离出更新的元素：

def find_updated_ids(arrA, arrB):
    # 建立元素到原数组索引的映射，快速查询位置
    pos_in_a = {val: idx for idx, val in enumerate(arrA)}
    n = len(arrB)
    current_min_pos = float('inf')
    split_idx = n  # 默认所有元素都是更新的
    
    # 从后往前遍历，定位未更新元素的起始点
    for i in reversed(range(n)):
        current_val = arrB[i]
        current_pos = pos_in_a[current_val]
        # 未更新元素在原数组中的索引应保持递增，从后往前看则是递减
        if current_pos < current_min_pos:
            current_min_pos = current_pos
        else:
            # 顺序不符合原数组，从此位置往前是更新元素
            split_idx = i + 1
            break
    
    return arrB[:split_idx]

# 测试示例
arrA = [1, 2, 3, 4, 5]
arrB = [3, 2, 1, 4, 5]
updated_ids = find_updated_ids(arrA, arrB)
print("更新的ID列表:", updated_ids)  # 输出: [3, 2]

逻辑说明 #

1. 索引映射：用字典pos_in_a记录每个元素在arrA中的索引，实现O(1)时间复杂度的位置查询。
2. 反向遍历：从arrB末尾开始遍历，维护current_min_pos记录已遍历元素在arrA中的最小索引——未更新元素的索引在arrA中是递增的，反向看则是递减的。
3. 定位分割点：当遇到元素索引不小于current_min_pos时，说明该元素属于更新后的前置部分，从此位置+1到数组末尾的元素都是未更新的。
4. 返回结果：arrB的前split_idx个元素即为被更新的ID列表。

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