wait 发表于 2015-12-1 21:13:57

找出数组中唯一的重复元素

          1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?


答案:根据异或运算的性质,相同元素异或,其值为0,相异元素异或其值非0,任何数与数字0进行异或运算,其结果为该数。本题中,正好可以使用到此方法,即将数组里的元素逐一异或,得到的值再与数字1、2、3……N异或,得到的最终结果即为所求的重复元素。
以数组序列{ 1, 3, 4, 2, 5, 3 }为例。(1^3^4^2^5^3)^(1^2^3^4^5)=(1^1)^(2^2)^(3^3^3)^(4^4)^(5^5)=0^0^3^0^0=3。示例代码如下所示。
#include<iostream>usingnamespace std; intFindDup(int* array, int len){            if(NULL==array || len<1)                        return -1;            int result = 0;            int i;            for (i = 0; i <len; i++)                        result ^= array;            for (i = 1; i <len; i++)                        result ^= i;            return result; } voidmain() {               int array[] = { 1, 3, 4, 2, 5, 3};            int len = sizeof(array) /sizeof(array);            cout << FindDup(array, len)<< endl;}
程序输出为
3

页: [1]
查看完整版本: 找出数组中唯一的重复元素