原题
1~n放在含有n+1个元素的数组中，只有唯一的一个元素值重复，其它均只出现
一次。要求时间复杂度O（n），空间复杂度O（1）。
题解（Java）
public class Repeat {
//利用求和作差求重复数
public static int getRepeatNumber1(int[] arr) {
if (arr == null) {
return -1;
} else {
//数组的长度为n+1,求1～n的和
int sum = 0;
int n = arr.length - 1;
if (n % 2 == 0) {
sum = (n + 1) * (n / 2);
} else {
sum = (n + 1) * (n / 2) + (n / 2 + 1);
}
int sumArr = 0;
for (int i = 0; i < arr.length; i++) {
sumArr += arr[i];
}
return sumArr - sum;
}
}
//利用异或求重复数
public static int getRepeatNumber2(int[] arr) {
if (arr == null) {
return -1;
} else {
//数组的长度为n+1,求1～n的异或结果
int orSum = 0;
int n = arr.length - 1;
//类似加法运算律，快速求1～n的异或结果
if (n % 4 == 0) {
orSum = n;
} else if (n % 4 == 1) {
orSum = 1;
} else if (n % 4 == 2) {
orSum = n + 1;
} else {
orSum = 0;
}
int orSumArr = 0;
for (int i = 0; i < arr.length; i++) {
orSumArr ^= arr[i];
}
return orSumArr ^ orSum;
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 3, 4};
int result = getRepeatNumber2(arr);
System.out.println(result);
}
}
思考
此题有两种解法。
1. 求数组的和，然后求1～n的和，二者作差，结果即为重复数，比较巧妙的想法。看过网上的讨论后，有人说其实这题想考的是异或运算的应用，后来才出现了这种奇妙的解法。不知道出此题的人当初是不是这么想的，还是挺有意思的。在面试的过程中，一开始其实我并没找到空间复杂度O（1）的解法，面试官给出了提示，说可考虑用异或去做。从这方面也可以说明此题的本意可能是为了考察异或运算的应用吧。
2. 关于异或运算的详细介绍，大家可以从网上查到。其主要的性质就是，两个相同的数异或结果为0，任何数异或0，结果为其本身，同时异或满足交换律和结合率。利用这几个性质就能解决此题。与解法1思路相同，首先求出1～n异或的结果，然后求出数组所有数字的异或结果，二者作异或运算，结果即为重复的数字。
证明：
记1～n异或结果为t1，重复的目标数字为k，那么数组的异或结果即为t1^k。二者异或结果为：t1^t1^k=k。
