这个题有多种思路。
- 使用Hash来解决问题。
在这个算法中，我们使用了一个辅助数组，数组中的元素是boolean类型，数组中元素的值用以表示某个值是否出现过。如果出现过，那么它的状态就设置为true。
Java代码的实现如下：
class findDuplicate {
public static int findDuplicate(int arr[]) {
int n = arr.length;
// 创建一个数组visited，用来存储是数字否存在的标志
// 也可以使用map代替
boolean visited[] = new boolean[n + 1];
// 遍历数组中的每个元素，并标志访问过的数据为true
// 如果元素之前出现过，则返回这个元素
for (int i = 0; i < n; i++) {
if (visited[arr[i]]) {
return arr[i];
}
visited[arr[i]] = true;
}
// 没找到
return -1;
}
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 4 };
System.out.println(findDuplicate(arr));
}
}
这种算法的时间复杂度是O(n)，空间复杂度也是O(n)。
- 我们还能使用常量空间（空间复杂度为O(1)）解决问题。既然数组中除了一个元素是重复之外，其他元素都是唯一的，并且元素的值在 1 到 n-1 之间，我们可以把数组的下标作为key，把元素取负数来判断元素是否重复。例如，对于每个元素 arr[i]，我们得到它的绝对值 abs(arr[i])，并修改下标为 abs(arr[i]) – 1 的这个元素的正负号。最后，我们再遍历一次数组，如果第 i 个元素的值是正数，那么重复的元素就是 i + 1。
上面的算法我们遍历了2次数组。其实，我们可以缩为1次。对于每一个元素 arr[i]，我们得到绝对值abs(arr[i])，然后反转第abs(arr[i])-1个元素的符号，如果准备反转符号的元素已经是负数了，那么它一定是那个重复的数字。
Java代码实现如下（此处我们只实现findDuplicate方法，不再重新创建类）：
public int findDuplicate(int arr[]) {
int n = arr.length;
int duplicate = -1;
for (int i = 0; i < n; i++) {
int absVal = (arr[i] < 0) ? -arr[i] : arr[i];
// 如果数组中，下标为 abs(arr[i]) - 1 的元素为正数，那么改变成负数
if (arr[absVal - 1] >= 0) {
arr[absVal - 1] = -arr[absVal - 1];
}
else {
// 如果已经是负数，说明它是重复元素
duplicate = absVal;
break;
}
}
// 恢复数组到初始值
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
arr[i] = -arr[i];
}
}
return duplicate;
}
这种算法的时间复杂度是O(n)，空间复杂度是O(1)。
- 这种方法和方法2类似。这种方案是对数组通过交换位置的方式进行从小到大的排序。因为数字是连续的，所以数组的第 i 个位置的值是 i + 1。在排序的过程中，如果要交换的两个数字是相等的，那么它就是重复的。
遍历数组，对于第 i 个元素：
- 如果它的值为 arr[i] 等于 i + 1，那么继续遍历下一个元素；
- 如果 arr[i] 等于 arr[arr[i] – 1 ]，那么它就是重复的数字；
- 如果不满足前面两个条件，则交换 arr[i] 与 arr[arr[i] – 1] 的值。
但这种方案会改变原始数组的内容，且无法恢复。当然，原题并没有提到不允许改变原始数据，这是常见编程规范的约定。相对而言，并没有方法2好，不推荐。
Java代码实现如下：
public int findDuplicate(int arr[] )
{
int num = 0;
int index = 0;
int len = arr.length;
while (index < len) {
num = arr[index];
// 如果位置的值等于自己本身，那么跳到下一个
if (num == index + 1) {
index++;
continue;
}
// 如果数值重合，则返回
if (arr[num - 1] == num) {
return num;
}
// 交换位置
arr[index] = arr[num - 1];
arr[num - 1] = num;
}
// 不会执行到这一步
return -1;
}
- 使用异或。
还可以使用异或（XOR）来解决问题。思路就是把所有的元素 1 到 n-1 的数都异或一次，由于a^a = 0, 0^0 = 0，a^0 = a。在这个异或中，重复的元素出现了3次，其他所有的元素都出现了2次，所以最后的值就是重复的元素。
Java代码实现如下：
public int findDuplicate(int arr[]) {
int n = arr.length;
int XOR = 0;
for (int i = 0; i < n; i++)
{
XOR ^= A[i];
}
for (int i = 1; i <= n - 1; i++)
{
XOR ^= i;
}
return XOR;
}
这种算法的时间复杂度是O(n)，空间复杂度是O(1)。
- 求和。
我们可以通过求和的方式解决问题：先计算出所有元素的和，然后再减去1到n-1的和，最后的值就是重复的数。这种方案最简单。
Java代码实现如下：
public int findDuplicate(int arr[]) {
int size = arr.length;
// int 会存在越界的情况，所以要转换成 long
// long 一定不会越界
long expected_sum = ((long) size) * (size - 1) / 2;
long actual_sum = 0;
for (int i = 0; i < size; i++) {
actual_sum += arr[i];
}
return (int) (actual_sum - expected_sum);
}
这种算法的时间复杂度是O(n)，空间复杂度是O(1)。
备注：本题来自《(4/500)从有限范围的数组中找出重复元素》，此次重新整理，进一步完善算法。
请你留言