首页 > 代码库 > 找出数组中唯一的重复元素
找出数组中唯一的重复元素
【问题】
1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。 每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?
【代码】
#include <stdio.h> #include <stdlib.h> #include <string.h> /*根据异或法的计算方式,每两个相异的数执行异或运算之后,结果为1; 每两个相同的数异或之后,结果为0,任何数与0异或,结果仍为自身。 所以数组a[N]中的N个数异或结果与1至N-1异或的结果再做异或, 得到的值即为所求。*/ int findRepeat1(int *a, int len) { int i, res; res = a[0]; for (i = 1; i < len; i++) { res ^= i; res ^= a[i]; } return res; } /*利用下标与单元中所存储的内容之间的特殊关系,进行遍历访问单元, 一旦访问过的单元赋予一个标记,利用标记作为发现重复数字的关键。*/ int findRepeat2(int *a, int len) { int index; index = a[len - 1] - 1; while (1) { if (a[index] < 0) break; a[index] *= -1; index = a[index] * (-1) - 1; } return index + 1; } int main(void) { int a[] = {1, 2, 3, 4, 5, 6, 4}; int res; res = findRepeat2(a, 7); printf("%d\n", res); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。