给定一个数组，它有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
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
// 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;
}
[/cpp]
Java语言实现：
[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));
}
}
[/java]
输出: 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
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;
}
[/cpp]
java语言实现：
[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));
}
}
[/java]
输出: Duplicate element is 2
以上两种方案的时间复杂度都是O(n)，空间复杂度都是o(1)。
3. 使用异或
我们还可以使用异或（XOR）来解决问题。思路就是把所有的元素和1到n-1的数都异或一次，由于a^a = 0, 0^0 = 0，a^0 = a。在这个异或中，所有的元素都出现了2次，而重复的元素出现了3次，所以最后的值就是重复的元素。
C++语言实现：
#include
using namespace std;
// Function to find a duplicate element in a limited range array
int findDuplicate(int A[], int n)
{
int XOR = 0;
// take xor of all array elements
for (int i = 0; i < n; i++)
XOR ^= A[i];
// take xor of numbers from 1 to n-1
for (int i = 1; i <= n-1; i++)
XOR ^= i;
// same elements will cancel out each other as a ^ a = 0,
// 0 ^ 0 = 0 and a ^ 0 = a
// xor will contain the missing number
return XOR;
}
// 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;
}
[/cpp]
java语言实现：
[java]
class findDuplicate
{
// Function to find a duplicate element in a limited range array
public static int findDuplicate(int A[])
{
// n is length of the array
int n = A.length;
int XOR = 0;
// take xor of all array elements
for (int i = 0; i < n; i++)
XOR ^= A[i];
// take xor of numbers from 1 to n-1
for (int i = 1; i <= n - 1; i++)
XOR ^= i;
// same elements will cancel out each other as a ^ a = 0,
// 0 ^ 0 = 0 and a ^ 0 = a
// xor will contain the missing number
return XOR;
}
// 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));
}
}
[/java]
输出: Duplicate element is 2
这种方法时间复杂度是O(n)，空间复杂度是O(1)。
4.求和
最后，我们可以通过求和的方式解决问题：先计算出所有元素的和，然后再减去1到n-1的和，最后的值就是重复的数。简单吧。:)
C++语言：
#include
#include
#include
template
int find_duplicate(It start, It finish)
{
auto size = std::distance(start, finish);
int actual_sum = std::accumulate(start, finish, 0);
int expected_sum = size * (size – 1) / 2;
return actual_sum – expected_sum;
}
int main()
{
std::array
std::array
std::cout << "The duplicate element is " <<
find_duplicate(arr1.begin(), arr1.end()) << '\n';
std::cout << "The duplicate element is " <<
find_duplicate(arr2.begin(), arr2.end()) << '\n';
}
[/cpp]
输出:
The duplicate element is 4
The duplicate element is 2
这种方法时间复杂度是O(n)，空间复杂度是O(1)。
请你留言