寻找数组中出现的唯一重复的一个数
题目:1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次.每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?
方法一:(当N为比较大时警惕溢出)将1001个元素相加减去1,2,3,……1000数列的和,得到的差即为重复的元素。
int findRepeat(int *a)
{
int i;
for (i = 0; i < 1001; i++)
{
a[1000] += a[i];
}
a[1000] -= (i*(i - 1)) / 2; //i的值为1001
return a[1000];
}
方法二:
原理:
设重复数为A,其余999个数异或结果为B。
1001个数异或结果为A^A^B
1-1000异或结果为A^B
由于异或满足交换律和结合律,且A^A=00^A=A;
则有
(A^B)^(A^A^B)=A^B^B=A
实现代码如下:
int findRepeat(int *src, int n)
{
for (int i = 1; i < n; ++i)
{
src[0] ^= (src[i] ^ i);
}
return src[0];
}
其中:src位存放数的数组, 你为数组元素的个数,在循环里面src[0] = src[0] ^ src[1]^...^src[n-1] ^ 1 ^ 2 ^ ...^ (n-1)
若是可以使用辅助空间, 我则会这么些上面的代码:
int findRepeat(int *src, int n)
{
register int result = src[0];
for (int i = 1; i < n; ++i)
{
result ^= (src[i] ^ i);
}
return result;
}
若有不清楚, 可以与我联系, 如有错误, 欢迎指出, 分享请表明出处, 谢谢
感觉好的话就顶一个, 感觉不错的话就踩一个。
分享到:
相关推荐
C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程C++/CLI教程
这年头,有个示例程序是多么的重要,节省了大量时间。
很好的,大家来看看 吧.初学的菜鸟来看看 吧其实我 是菜鸟啊啊
C/C++ threadpool封装, 线程池, Linux, 多线程, pthread
此程序使用的是#define创建的函数来作为储存的不可直接用于(if)判断
c++基础c++类,类的实例,类的指针,成员函数,构造函数.,适合新手菜鸟小白看,
使用的是C++编写的智能快递柜,无前端页面,只在工作台使用
RC4加密,想用的下吧,虽然是菜鸟,但觉得自己写的这个还不错
内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存管理在C++中无处不在,内存泄漏几乎在每个C++...
职场菜鸟需要注意的一些细节问题,一定会对你有所帮助!
c++ builder经典入门 对于刚接触的菜鸟来说非常有用
c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮c++菜鸟的摇篮
同时标准化委员会声明就有的C++头文件将不再列于被支持的名单之中了,而旧有的C头文件为了满足“对C的兼容性”这个古老契约,仍然将继续存活下去。 但是,那些编译器厂商不可能去推翻他们客户的旧有编译器(也跟本...
c++基础知识 适合初学者 内容全面 菜鸟必看
菜鸟教程(Runoob)提供的免费网上编译器! 包含C++ C C# HTML/CSS/JavaScript PHP Python等许多语言的编译器! 还有画图 进制转换等常用工具! 还有资源共享! 欢迎来到(http://c.runoob.com)!
包含选择题,填空题以及上机操作题。比如 下述程序的输出结果是()。 int x = 10; y = x++; printf(“%d, %d”, (x++, y), y++); A、11, 10 B、11, 11 C、10, 10 D、10, 11 试卷考查应试者的c语言能力,
师兄推荐的研究生找工作前必看的书。教你如何从菜鸟进化为编程高手。
这是本人刚入职作的作业,因为刚毕业,所以写的代码基本不能看,也希望各位能点评一下,自己刚学习,哎,还有好多考虑到,希望大家可以帮我找下bug和优化下代码,谢谢了! 自己是刚毕业工作的学生,所以写得很laji...
我们大学上课老师的讲课内容。。。 我们老师很牛逼,觉得清华教材讲的很深,不利于全然不会的弱弱弱菜鸟学习。。 便,自创C++教材,,,供我们学习~ *注意:要有C语言基础*
c语言菜鸟必看代码c语言菜鸟必看c语言菜鸟必看代码代码