找出极限运动

来源：蜘蛛抓取(WebSpider) 时间：2011-10-12 12:57 标签： 极限运动
Posts - 84,
Articles - 0,
Comments - 1841
对月狂饮，惊叹青春过半。顾镜自怜，提眉强作欢颜。
16:39 by 鹤冲天, ... 阅读,
这是园子里讨论了好长时间的题目了：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？发起文章：&作者： &算法改进：& 作者：莫贝特给出的算法是：将所有数加起来，减去1+2+...+1000的和Ivony给出的算法是:& 将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数两位算法的时间复杂度都是: 2n (莫贝特的算法可以用高斯算法简化)我把题目扩展了一下，将1000换成n，让些题更通用一些：1-n放在含有n+1个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？（n可能为奇数）（注意：数组是无序的，有序数组很好解决不讨论）下面是我的算法，先给出代码，c#语言
&&&&&&&&/**////&&summary&&&&&&&&&///&查找重复的数&&&&&&&&///&&/summary&&&&&&&&&///&&param&name="ints"&<span style="color: #..n无序序列加上1..n之间的一个数&/param&&&&&&&&&///&&returns&重复的数&/returns&&&&&&&&&public&static&int&GetRepeated(int[]&array)&&&&&&&&{&&&&&&&&&&&&int&temp&=&<span style="color: #;&&&&&&&&&&&&foreach&(int&i&in&array)&&&&&&&&&&&&&&&&if&(i&%&<span style="color: #&==&<span style="color: #)&temp&+=&i&+&<span style="color: #;&&&&&&&&&&&&&&&&else&temp&-=&i;&&&&&&&&&&&&if&(array.Length&%&<span style="color: #&==&<span style="color: #)&temp&-=&array.L//n为奇数要处理一下&&&&&&&&&&&&return&temp&&&<span style="color: #&?&-temp&:&temp&-&<span style="color: #;&&&&&&&&}原理如下（n为偶数时）：(1-2)+(3-4)+(5-6)+(7-8)+....+(n-1 - n)& 等于多少？先不管，再改进一下((1+1)-2)+((3+1)-4)+((4+1)-5)+((5+1)-6)+...+((n-1+1) - n) 等于多少？零！这个公式证明初中生都会！这是有序序列，对无序的情况我们可以这样理解：从数组中依次读数，如果读到是奇数则加上再加1,如果偶数则减去。和代码中的foreach对照一下吧，应该比较好理解！函数中倒数第二行对n是奇数的情况作了些处理。最后返回处理：&&&&&&如果重复的数是偶数，则肯定被减了，则返回它的负值-&&&&&&如果重复的数是奇数，则肯定被加了，而且还多加了1, 返回 temp-1。这个算法时间复杂度是n，空间复杂度是1，代码行数是6，原理也简单。利用初中（小学奥赛估计也会）的知识解决一个算法问题，感觉算不上高手。只能感叹我们以前的知识忘记了太多了！----------------------------------------------------------------------------------------------------------刚才又看前面两篇帖子的回复，发现了&提供的一个算法，本人修正了一下：
&&&&&&&&public&static&int&GetRepeated2(int[]&array)&&&&&&&&{&&&&&&&&&&&&int&temp&=&<span style="color: #;&&&&&&&&&&&&for&(int&i&=&<span style="color: #;&i&&&array.L&i++)&&&&&&&&&&&&&&&&temp&+=&array[i]&-&i&;&&&&&&&&&&&&return&temp;&&&&&&&&}算法原理：改进莫贝特的算法，加减加减加减...，而不是（加加加...）减（加加加...）。出现溢出的可能性也小了很多！更是精简，强人！！不甘落后，我用lambda再改进一下：
&&&&&&&&public&static&int&GetRepeated3(int[]&array)&&&&&&&&{&&&&&&&&&&&&return&array.Select((i,&j)&=&&i&-&j).Sum();&&&&&&&&}简单说明一下：&&&&&&方法三中的&#8220;i&#8221;相当与方法二中的&#8220;array[i]&#8221;；&&&&&&方法三中的&#8220;j&#8221;相当于方法二中的&#8220;i&#8221;其它大可不必写成一个函数，像下面这样直接调用就好了，也算是最后的极限算法了。
&&&&int&repeatedNum&=&array.Select((i,&j)&=&&i&-&j).Sum();array就是包含n+1个数的数组，repeatedNum就是其中唯一重复的数。这应该是极限了吧!大家可以调试运行一下这几种方法都可以通过，有问题拍我。
本人系列文章《》，敬请关注！高数极限问题 观察下列数列的变化趋势,写出极限.求详解,&
为您推荐：
其他类似问题
扫描下载二维码为你推送和解读最前沿、最有料的科技创投资讯
36Kr股权投资
汇集行业内最优质创业项目的股权投资平台
聚集15家顶级投资机构的专业互联网融资平台
聚集全球最优秀的创业者，项目融资率接近97%，领跑行业

我要回帖

更多关于 极限运动 的文章

 

随机推荐