编程之美 N个正整数的数组寻找丢失的数和寻找唯一重复的数

54 阅读 0 评论 36 点赞

我是靠谱客的博主幸福黄蜂，最近开发中收集的这篇文章主要介绍编程之美 N个正整数的数组寻找丢失的数和寻找唯一重复的数，觉得挺不错的，现在分享给大家，希望可以做个参考。

①n-1个整数，并未排序，元素师1~n中不同整数如何寻找序列中缺少的整数？请写一个线性的算法。

思想：

首先，求得所有元素的和SUM，T=O（n）

再计算N个数的和为n（n+1）/2

所以缺少的整数为： n（n+1）/2 - SUM

②n+1个整数，并未排序，元素师1~n中不同整数如何寻找序列中唯一重复的数？

解法一：类似于上面的求和解法，SUM - n（n+1）/2

解法二：异或法：

for(int i :0->n)

{

tmp =0^a[i]; //因为j^j=0,所以这步骤是消除了重复的数

tmp^=i; //把所有tmp的N个数异或，只有重复的数没被异或掉

}

解法三：位图（略）

解法四：hash

解法五：将数组改写成链表，然后类似于单链表找环，设置两个指针，一快一慢（快：f=p->next->next；慢：s= p-next;），去找环的点（即重复的数）

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

编程之美 N个正整数的数组 寻找丢失的数 和 寻找唯一重复的数