C语言实现查找替换数字：时间复杂度O(N)空间复杂度O(1)

题目描述：

有N个不同的数，分别是1到N，在随机打乱顺序的过程中，出现了一点小误差，其中一个数换成了另一个数。请你找出谁替换了谁，要求时间复杂度是O(N)，辅助空间O(1），这意味不能使用数组、map、set、vector等。

输入：

N个数ai（1<=ai<=N）,其中缺了一个，而又有一个数出现了2次，其它都出现了1次，数之间有一个空格。（N<2000）

输出：

两个整数a和b(a是缺的哪一个，b是出现两次的那一个），中间有一个空格，没有回车

输入样例：

2 3 4 1 3 6

输出样例：

5 3

思路：

本题是典型的鸽巢原理，因为有N个数，其中缺了一个，又有一个数出现了2次，所以N个数中必有一个数没有出现，一个数出现了2次。那么，只要通过异或运算（异或运算的性质请自行百度）找出出现两次的数，然后再遍历一次数组，找出缺的那个数即可。

代码：

#include <stdio.h>

int main() {
    int N, i, a, b, sum = 0;
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
        sum ^= i;
    }
    for (i = 1; i <= N - 1; i++) {
        int temp;
        scanf("%d", &temp);
        sum ^= temp;
    }
    b = sum;
    for (i = 1; i <= N - 1; i++) {
        int temp;
        scanf("%d", &temp);
        if (temp == b) {
            a = i + 1;
            break;
        }
    }
    printf("%d %d", a, b);
    return 0;
}