返回首页
当前位置: 主页 > 网络编程 > .Net实例教程 >

数组a[n]中存放1-n中的n-1个数,给出算法找出重复的那一个数

时间:2012-05-22 16:29来源:知行网www.zhixing123.cn 编辑:麦田守望者

问题描述:

数组a[n]中存放1-n中的n-1个数,给出算法找出重复的那一个数。



算法一:

对数组a[n]进行冒泡排序,如果冒泡所得的最值和前一个最值相等,则该最值为重复的数。



分析:

该算法时间复杂度最坏的情况为O(n的2次方),在空间开销上只需要一个额外的交换空间。



如何将时间开销减小呢?下面给出另外一种算法



算法二:

给定另外一个数组b[n],将a[n]中的数作为数组b的索引,然后遍历b[n],如果未访问过,则标记;如果已经访问过,则该索引就为重复的数。



分析:

该算法时间复杂度能够达到最好的情况O(n),只是需要在空间上额外需要数组b[n]大小的空间。



但是在n越来越大的情况下,用空间上的开销来将时间复杂度从平方级降到O(n)是非常有必要的。



延伸:

如何在上面基础上找出1-n中没有的那个数,此时只需在算法二的基础上对b[n]进行全遍历,未被访问过的地址的索引则为1-n中没有的那个数。
 

------分隔线----------------------------
标签(Tag):数据库 SQLServer SQLServer数据库 Sqlserver2008
------分隔线----------------------------
推荐内容
猜你感兴趣