当前位置:  技术问答>linux和unix

大家练练算法吧..>@

    来源: 互联网  发布时间:2016-02-06

    本文导语:  数组a[N],存放了1至N-1个数,其中某个数重复一次。写一个函数,找出被重复的数字.时间复杂度必须为o(N)函数原型: int do_dup(int a[],int N) | o(N)的时间必然以巨大的空间消耗为代价。 分配一个足...

数组a[N],存放了1至N-1个数,其中某个数重复一次。写一个函数,找出被重复的数字.时间复杂度必须为o(N)函数原型:

int do_dup(int a[],int N)

|
o(N)的时间必然以巨大的空间消耗为代价。

分配一个足够大的空间,对空间与数之间进行匹配,这个匹配取决于数的取值范围。

如果输入的数是0-65535之间的整数,那么只要65536个空间,分别记录这65535个数出现的次数,线性扫描,将当前数的关联空间加一,如果为2,则表示出现重复。

如果输入的数是0-65535之间的小数,有效数字1位,那么需要65535*10个空间,空间标号与数的匹配函数就是 f(x) = x * 10....

依此类推.......如果允许分配的空间足够大,就可以在o(N)时间内完成该需求。

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 想好好学习c++,想找个开源项目练练手,大家推荐一下
  • 学完网络编程,想做个项目练练手,大家有什么建议
  • 《unix网络编程》看了一大半,想写个东西来练练手。
  • 网络技术 iis7站长之家
  • **********谁能给我一分需求文档?我想练练uml和Java***********
  • 请问,哪里有可以用的aix server,我想练练,熟悉熟悉,要支持telnet的,
  • 想做一个xml的项目练练手,不知作什么好,请较各位大侠
  • 小和尚想学JAVA了!看了一段时间书!开下载JDK来练练了!谁知道再那里下载JDK1.3或1.4啊?


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3