寻找替换的数字 - 时间复杂度O(N)，空间复杂度O(1)

分析

题目中只有一个数替换了另一个数，那么每个数都应该在对应的位置上，只有一个数在错误的位置上。我们可以遍历整个序列，如果第 i 个位置上的数不是 i + 1，那么就是该位置上的数发生了替换。

遍历到第 i 个位置，若 ai != i+1，我们需要判断 ai 出现了几次。如果 ai 出现了两次，那么应该是 ai 替换了 i+1；若 ai 出现了一次，那么应该是 i+1 替换了 ai。

为了避免使用数组，我们可以将已经遍历过的数和当前数作异或操作，相同的数异或后为 0，不相同的数异或后为非 0 值。因此，我们可以用一个变量 x 记录遍历过的数和当前数的异或值。如果 ai 出现了一次，那么将 x 和 i+1 异或，如果 ai 出现了两次，那么将 x 和 ai 异或。最后遍历完后，x 的值是 a^b，其中 a 是缺失的数，b 是出现两次的数。

时间复杂度：O(n)，空间复杂度：O(1)。

代码

N = int(input())
x = 0
for i in range(N-1):
    ai = int(input())
    if ai == i+1:
        x ^= ai
    else:
        if ai == x:
            x ^= ai
        else:
            x ^= (i+1)
print(x, end=' ')  # 此时 x 的值为 a^b

for i in range(N-1):
    ai = int(input())
    if ai == x:
        print(ai)
        break