给定一个数组，它有n个元素，数组中包含1到n-1这些值。在这个数组中，除了一个元素是重复的，其他元素都只出现了一次。请找出重复的元素。
例如，
输入: { 1, 2, 3, 4, 4 }
输出:The duplicate element is 4
输入:{ 1, 2, 3, 4, 2 }
输出:The duplicate element is 2
1. 通过Hash来计算
这种算法的思想是使用Hash来解决问题。在这个算法中，我们使用了一个辅助数组，数组中的元素是boolean类型，数组中元素的值用以表示某个值是否出现过。如果出现过，那么就返回true。
C++语言实现：
#include <iostream>
using namespace std;
// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n){
// create an visited array of size n+1
// we can also use map instead of visited array
bool visited[n];
fill(visited, visited + n, 0);
// sets every value in the array to 0</iostream></p>
// for each element of the array mark it as visited and
// return the element if it is seen before
for (int i = 0; i < n; i++) {
// if element is seen before
if (visited[arr[i]]) return arr[i];
// mark element as visited
visited[arr[i]] = true;
}
// no duplicate found
return -1;
}
main function int main() {
// input array contains n numbers between [1 to n - 1]
// with one duplicate
int arr[] = { 1, 2, 3, 4, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Duplicate element is " << findDuplicate(arr, n);
return 0;
}
Java语言实现：
class findDuplicate {
// Function to find a duplicate element in a limited range array
public static int findDuplicate(int arr[]) {
// n is length of the array
int n = arr.length;
// create an visited array of size n+1
// we can also use map instead of visited array
boolean visited[] = new boolean[n + 1];
// for each element of the array mark it as visited and
// return the element if it is seen before
for (int i = 0; i < n; i++) {
// if element is seen before
if (visited[arr[i]]) return arr[i];
// mark element as visited
visited[arr[i]] = true;
}
// no duplicate found
return -1;
}
// main function
public static void main (String[] args) {
// input array contains n numbers between [1 to n - 1]
// with one duplicate
int arr[] = { 1, 2, 3, 4, 4 };
System.out.println("Duplicate element is " + findDuplicate(arr));
}
}
输出: Duplicate element is 4
以上两种方案的时间复杂度都是O(n)，空间复杂度都是o(n)。
2
我们还能使用常量空间（空间复杂度为O(n)）解决问题。既然数组中除了一个元素是重复之外，其他元素都是唯一的，并且元素的值在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个元素的符号，如果准备反转符号的元素已经是负数了，那么它一定是那个重复的数字。
C++语言实现：
#include <iostream>
using namespace std;
// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n){
int duplicate = -1;
// do for each element in the array
for (int i = 0; i < n; i++) {
// get absolute value of current element
int absVal = (arr[i] < 0) ? -arr[i] : arr[i];
// make element at index abs(arr[i])-1 negative if it is positive
if (arr[absVal - 1] >= 0)
arr[absVal - 1] = -arr[absVal - 1];
else{
// if element is already negative, it is repeated
duplicate = absVal;
break;
}
}
// restore original array before returning
for (int i = 0; i < n; i++) {
// make negative elements positive
if (arr[i] < 0) arr[i] = -arr[i];
}
// return duplicate element
return duplicate;
}
// main function
int main() {
// input array contains n numbers between [1 to n - 1]
// with one duplicate
int arr[] = { 1, 2, 3, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Duplicate element is " << findDuplicate(arr, n);
return 0;
}
java语言实现：
class findDuplicate {
// Function to find a duplicate element in a limited range array
public static int findDuplicate(int arr[]) {
// n is length of the array
int n = arr.length;
int duplicate = -1;
// do for each element in the array
for (int i = 0; i < n; i++) {
// get absolute value of current element
int absVal = (arr[i] < 0) ? -arr[i] : arr[i];
// make element at index abs(arr[i]) - 1 negative
// if it is positive
if (arr[absVal - 1] >= 0)
arr[absVal - 1] = -arr[absVal - 1];
else{
// if element is already negative, it is repeated
duplicate = absVal;
break;
}
}
// restore original array before returning
for (int i = 0; i < n; i++) {
// make negative elements positive
if (arr[i] < 0) arr[i] = -arr[i];
}
// return duplicate element
return duplicate;
}
// main function
public static void main (String[] args) {
// input array contains n numbers between [1 to n - 1]
// with one duplicate
int arr[] = { 1, 2, 3, 4, 4 };
System.out.println("Duplicate element is " + findDuplicate(arr));
}
}
输出: Duplicate element is 2
以上两种方案的时间复杂度都是O(n)，空间复杂度都是o(1)。
3. 使用异或
我们还可以使用异或（XOR）来解决问题。思路就是把所有的元素和1到n-1的数都异或一次，由于a^a = 0, 0^0 = 0，a^0 = a。在这个异或中，所有的元素都出现了2次，而重复的元素出现了3次，所以最后的值就是重复的元素。
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.求和
最后，我们可以通过求和的方式解决问题：先计算出所有元素的和，然后再减去1到n-1的和，最后的值就是重复的数。简单吧。:)
代码略。
输出:
The duplicate element is 4
The duplicate element is 2
这种方法时间复杂度是O(n)，空间复杂度是O(1)。
备注：本文为初始版本，在《算法题：有限范围的数组中找出重复元素》中重新整理，进一步完善，提供更多的算法。
请你留言