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

//数组之找出数组中唯一重复的元素：将1到N-1这N-1个数放入数组a[N]中,其中某个数重复一次，找出重复的数字； //注意该数组的特性是：数组中的数是连续的； //要求1）每个元素只访问一次，2）不能用辅助空间； //方法一：遍历数组，依次比较，但不符合条件一； //方法二：数组求和法；因为只有一个数字重复一次，而数又是连续的，根据累加和原理，对数组的所有元素求和, // 然后减去1至N-1的和，即为所求的重复数； #include<iostream> using namespace std; int getDuplicates(int *nums,int len) { if(nums==nullptr||len<=0) return 0 ; int nSum=len*(len-1)/2; int sum=0; for(int i=0;i<len;i++) { sum+=nums[i]; } return (sum-nSum); } int main() { int nums[]={1,2,2,3,4,5,6,7,8,9,10,11,12}; int len=(sizeof(nums)/sizeof(nums[0])); int dupNum=getDuplicates(nums,len); cout<<dupNum<<endl; system("pause"); return 0; } //若无上述要求； //方法一：异或法；根据异或运算，每两个相同的异或结果为0； // 所以数组中N个数异或的结果再与（1至N）异或的结果相异或，得到的结果即为所求； int getDuplicates(int *nums,int len) { if(nums==nullptr||len<=0) return 0 ; int results=0; int i; for(i=0;i<len;i++) { results^=nums[i]; } for(i=1;i<=len-1;i++) { results^=i; } return results; } //方法二：位图法。原理：先申请一个长度为N-1且均为‘0’组成的数组，然后从头开始遍历数组， // 取每个数组元素的值，将其对应字符串中响应位置置1；若果已经置过1，则该数就是重复的数； // 时间复杂度为O(N)，空间复杂度为O(N)； int getDuplicates(int *nums,int len) { if(nums==nullptr||len<=0) return 0 ; int results=0; int *numsFlag=new int [len-1]; int i=1; while(i<len) { numsFlag[i]=0; i++; } for(i=0;i<len;i++) { if(numsFlag[nums[i]]==0) numsFlag[nums[i]]=1; else { results=nums[i]; break; } } return results; } //方法三：hash表 （数组可无序）时间复杂度为O(N)，空间复杂度为O(N)； int getDuplicates(int *nums,int len) { if(nums==nullptr||len<=0) return 0 ; int results=0; map<int,int> maping; for(int i=0;i<len;i++) { maping[nums[i]]++; if(maping[nums[i]]==2) { results=nums[i]; break; } } return results; } //变形：将1到N-1这N-1个数放入数组a[N]中,至少存在一个重复数，即可能存在多个重复数，O(N)时间里找出其中任意一个重复数， //注意该数组的特性是：数组中的数是连续的； 方法一：位图法，使用大小为N的位图，记录每个元素是否出现过，一旦遇到一个已经出现的元素，直接将 之输出； 时间复杂度为O(N)，空间复杂度为O(N)； 方法二：hash表； 时间复杂度为O(N)，空间复杂度为O(N)； 方法三： 数组排序法；首先对数组进行计数排序，然后顺序遍历数组，直到遇到一个已经出现的元素，直接将之输出。 时间复杂度为O(N)，空间复杂度为O(N)；