题目:
数组a[N],1至N-1这N-1个数存放在a[N]中,其中某个数重复一次。写一个函数,找出被重复的数字。
方法一:异或法。
数组a[N]中的N个数异或结果与1至N-1异或的结果再做异或,得到的值即为所求。
代码:
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include<time.h>
- void xor_findDup(int * a,int N)
- {
- int i;
- int result=0;
- for(i=0;i<N;i++)
- {
- result ^= a[i];
- }
-
- for (i=1;i<N;i++)
- {
- result ^= i;
- }
-
- printf("%d\n",result);
-
- }
-
-
-
- int main(int argc, char* argv[])
- {
- int a[] = {1,2,1,3,4};
- xor_findDup(a,5);
- return 0;
- }
方法二:数学法。
对数组的所有项求和,减去1至N-1的和,即为所求数。
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include<time.h>
- void xor_findDup(int * a,int N)
- {
- int tmp1 = 0;
-
- int tmp2 = 0;
-
- for (int i=0; i<N-1; ++i)
-
- {
-
- tmp1+=(i+1);
-
- tmp2+=a[i];
-
- }
- tmp2+=a[N-1];
- int result=tmp2-tmp1;
- printf("%d\n",result);
-
- }
-
-
-
- int main(int argc, char* argv[])
- {
- int a[] = {1,2,4,3,4};
- xor_findDup(a,5);
- return 0;
- }
对于求和,可以直接根据公式定义一个宏。#define sum(x) (x*(x+1)/2)
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include<time.h>
- #define sum(x) (x*(x+1)/2)
- void xor_findDup(int * a,int N)
- {
- int tmp1 = sum((N-1));
- int tmp2 = 0;
-
- for (int i=0; i<N; ++i)
- {
- tmp2+=a[i];
- }
- int result=tmp2-tmp1;
- printf("%d\n",result);
- }
-
- int main(int argc, char* argv[])
- {
- int a[] = {1,2,4,2,3};
- xor_findDup(a,5);
- return 0;
- }
方法三:标志数组法
申请一个长度为n-1且均为'0'组成的字符串。然后从头遍历a[n]数组,取每个数组元素a[i]的值,将其对应的字符串中的相应位置置1,如果已经置过1的话,那么该数就是重复的数。就是用位图来实现的。 如果考虑空间复杂度的话,其空间O(N)
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include<time.h>
- #define sum(x) (x*(x+1)/2)
- void xor_findDup(int * arr,int NUM)
- {
- int *arrayflag = (int *)malloc(NUM*sizeof(int));
- int i=1;
-
- while(i<NUM)
- {
- arrayflag[i] = false;
- i++;
- }
-
- for( i=0; i<NUM; i++)
- {
- if(arrayflag[arr[i]] == false)
- arrayflag[arr[i]] = true;
-
- else
- {
- printf("%d\n",arr[i]);
- return ;
- }
-
- }
- }
-
- int main(int argc, char* argv[])
- {
- int a[] = {1,3,2,4,3};
- xor_findDup(a,5);
- return 0;
- }
方法四:固定偏移量法
a[N],里面是1至N-1。原数组a[i]最大是N-1,若a[i]=K在某处出现后,将a[K]加一次N,做标记,当某处a[i]=K再次成立时,查看a[K]即可知道K已经出现过。该方法不用另外开辟O(N)的内存空间,但是在查重之后要将数组进行恢复。
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- #include<time.h>
- void xor_findDup(int * arr,int NUM)
- {
- int temp=0;
- for(int i=0; i<NUM; i++)
- {
-
- if(arr[i]>=NUM)
- temp=arr[i]-NUM;
- else
- temp=arr[i];
-
- if(arr[temp]<NUM)
- {
- arr[temp]+=NUM;
- }
-
- else
- {
- printf("有重复 %d\n",temp);
- return;
- }
- }
-
- printf("无重复");
- return ;
- }
- void clear(int *data,int num)
- {
- for(int i=0;i<num;i++)
- {
- if(data[i]>num)
- data[i]-=num;
- }
-
- }
- int main(int argc, char* argv[])
- {
- int a[] = {2,4,3,4,1};
- xor_findDup(a,5);
- clear(a,5);
- return 0;
- }
方法五:符号标志法
上个方法出现后是加N,也可以出现后加个负号,就是符号标志法。
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <math.h>
- #include<time.h>
-
- void xor_findDup(int * arr,int NUM)
- {
- int temp=0;
- for(int i=0; i<NUM; i++)
- {
- if(arr[i]<0)
- temp=0-arr[i];
- else
- temp=arr[i];
- if(arr[temp]>0)
- {
- arr[temp]=0-arr[temp];
- }
- else
- {
- printf("有重复 %d\n",temp);
- return;
- }
- }
- printf("无重复");
- return ;
- }
- void clear(int *data,int num)
- {
- for(int i=0;i<num;i++)
- {
- if(data[i]<0)
- data[i]=0-data[i];
- }
- }
- int main(int argc, char* argv[])
- {
- int a[] = {3,2,1,4,1};
- xor_findDup(a,5);
- clear(a,5);
- return 0;
- }
以上的方法对数组元素的值的范围是有限制的,如果数组元素的值不是在1至N-1范围时,可以先求出数组元素的最大值。
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <math.h>
- #include<time.h>
-
- int do_dup_mal(int arr[], int n, int *pre, int *back)
- {
- int MAX = -1;
- int i = 0;
- int sameVal = -1;
- *pre = *back = -1;
-
- for (int j=0; j<n; j++)
- {
- if (arr[j] > MAX) MAX = arr[j];
- }
-
- char *arrayflag = new char[MAX+1] ;
- if (NULL == arrayflag)
- return -1;
- memset(arrayflag, 0, MAX+1 );
- for(i=0; i<n; i++)
- {
- if(arrayflag[arr[i]] == '\0')
- arrayflag[arr[i]] = '\1';
- else
- {
- sameVal = arr[i];
- *back = i;
- break;
- }
- }
- delete[] arrayflag;
- if (i < n)
- {
- for (int j=0; j<n; j++)
- {
- if (sameVal == arr[j])
- {
- *pre = j;
- return true;
- }
- }
- }
- return false;
- }
-
-
-
-
-
- void main(int argc, char *argv[])
- {
- int prePos = -1, backPos = -1;
- int myArry[11];
- myArry[0] = 1;
- myArry[1] = 3;
- myArry[2] = 3;
- myArry[3] = 4;
- myArry[4] = 5;
- myArry[5] = 22;
- myArry[6] = 7;
- myArry[7] = 13;
- myArry[8] = 9;
- myArry[9] = 2;
- myArry[10] = 12;
-
-
- if (do_dup_mal(myArry, 11, &prePos, &backPos) )
- printf("%d\n",myArry[prePos]);
- }
-
转:http://buptdtt.blog.51cto.com/2369962/749049
posted on 2014-03-27 19:40
fly 阅读(525)
评论(0) 编辑 收藏 所属分类:
算法