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

找出替换的数 - 时间复杂度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

思路：

这道题其实非常简单，只要你找到了一个非常巧妙的思路。

我们假设缺失的数是x，重复的数是y。

那么我们将这N个数加起来，再减去1+2+...+N，这个差值记为sum1，然后我们把x,y两个数分别减去再加上，这个差值记为sum2。

那么x=y-(sum1-sum2)。因为x和y相差1，所以我们可以得到y=x+1。

这样我们就可以通过sum1和sum2计算出x和y。

代码：

#include <stdio.h>

int main() {
    int sum1 = 0, sum2 = 0, n, tmp;
    while (scanf("%d", &tmp) != EOF) {
        sum1 += tmp;
        sum2 += tmp * tmp;
    }
    n = (sum1 + 1) * sum1 / 2;
    sum1 = n - sum1;
    sum2 = n * (n + 1) / 2 - sum2;
    printf("%d %d", sum1 + sum2, sum1 + sum2 + 1);
    return 0;
}

解释：

1. sum1 记录所有输入数字的总和，sum2 记录所有输入数字的平方和。
2. 计算 1 到 N 的总和 n，并将它减去 sum1，得到缺失数字和重复数字的差值。
3. 计算 1 到 N 的平方和，并减去 sum2，得到缺失数字和重复数字的平方差。
4. 利用差值和平方差求解缺失数字和重复数字。

注意：

代码中没有使用任何数组、map、set、vector 等数据结构，满足空间复杂度 O(1) 的要求。代码中使用了 while 循环，每次循环读取一个数字，直到读取到文件结束符 EOF，时间复杂度为 O(N)。