给定一个数组,它有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); }输出: Duplicate element is 2
这种方法时间复杂度是O(n),空间复杂度是O(1)。
4.求和
最后,我们可以通过求和的方式解决问题:先计算出所有元素的和,然后再减去1到n-1的和,最后的值就是重复的数。简单吧。:)
代码略。
输出:
The duplicate element is 4
The duplicate element is 2
这种方法时间复杂度是O(n),空间复杂度是O(1)。
备注:本文为初始版本,在《算法题:有限范围的数组中找出重复元素》中重新整理,进一步完善,提供更多的算法。
请你留言