原题
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。
网友评论