菜鸟系列之C/C++经典试题(九)

你的名字 2022-08-12 00:20 37阅读 0赞

**寻找数组中出现的唯一重复的一个数**

题目：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 = 0 0^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;
    }

若有不清楚， 可以与我联系， 如有错误， 欢迎指出， 分享请表明出处， 谢谢

感觉好的话就顶一个， 感觉不错的话就踩一个。

发表评论取消回复

表情：

评论列表（有 0 条评论，37人围观）

还没有评论，来说两句吧...

相关阅读

相关菜鸟系列之C/C++经典试题(十)

打印1到最大的n位数题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印1， 2， 3，…，999. 方法一：这道题一看感觉很简单，首先求的n位

本是古典何须时尚/ 2022年08月12日 00:21/ 0 赞/ 140 阅读

相关菜鸟系列之C/C++经典试题(九)

寻找数组中出现的唯一重复的一个数题目：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次．每个数组元素只能访问一次，设计一个算法，将它找

你的名字/ 2022年08月12日 00:20/ 0 赞/ 38 阅读

相关菜鸟系列之C/C++经典试题(八)

计算二进制中1的个数题目：位运算方面的编程很少遇到，但也是很重的一个只是点，一个比较常见的题目就是计算一个数的二进制表示中的1的个数。分析：一个1都没有就是0，我们的

灰太狼/ 2022年08月12日 00:19/ 0 赞/ 162 阅读

相关菜鸟系列之C/C++经典试题(七)

找含单链表的环入口点问题1：如何判断单链表中是否存在环（即下图中从结点E到结点R组成的环）？ ![SouthEast][] 分析：设一快一慢两个指针（Node \

阳光穿透心脏的1/2处/ 2022年08月12日 00:07/ 0 赞/ 158 阅读

相关菜鸟系列之C/C++经典试题(六)

含有指针成员的类的拷贝题目：下面是一个数组类的声明与实现。请分析这个类有什么问题，并针对存在的问题提出几种解决方案。 template<typename T> c

淡淡的烟草味﹌/ 2022年08月11日 17:59/ 0 赞/ 148 阅读

相关菜鸟系列之C/C++经典试题(五)

求圆圈中剩下的最后一个数字题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字

超、凢脫俗/ 2022年08月11日 16:52/ 0 赞/ 142 阅读

相关菜鸟系列之C/C++经典试题(四)

题目一：查找最小的k个元素输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。分析：这道题最

你的名字/ 2022年08月11日 09:29/ 0 赞/ 172 阅读

相关菜鸟系列之C/C++经典试题(三)

设计包含min函数的栈题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。分析：这是200

墨蓝/ 2022年08月11日 05:30/ 0 赞/ 152 阅读

相关菜鸟系列之C/C++经典试题(二)

求子数组的最大和题目描述：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度

﹏ヽ暗。殇╰゛Y/ 2022年08月11日 05:30/ 0 赞/ 166 阅读

相关菜鸟系列之C/C++经典试题(一)

这个我写菜鸟系列之C/C++ 的第一篇文章题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。　　比如将二元

秒速五厘米/ 2022年08月11日 04:59/ 0 赞/ 218 阅读