新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 算法理论与分析 』 → [讨论]一道oxford计算机系算法设计题 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 15181 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [讨论]一道oxford计算机系算法设计题 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     aariel 美女呀，离线，快来找我吧！
      
      
      等级：大一新生
      文章：0
      积分：52
      门派：XML.ORG.CN
      注册：2006/4/27

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给aariel发送一个短消息 把aariel加入好友 查看aariel的个人资料 搜索aariel在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看aariel的博客楼主
    发贴心情 [讨论]一道oxford计算机系算法设计题

    you have a computer file containing 1,000,000 non-negative integers, in no particular order.?Imagine that they are the membership numbers of people who are enrolled in my internet club.?A new person wants to join the club, and we need to find an unused number to allocate to them.?How would you find, in a reasonable time, a number that was not already in the file?

    大家什么想法？


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/27 9:25:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第2楼
    发贴心情 
    我觉得可以扫描一篇这个数组，记录其中最大的数（这只需要n次读取和n-1次比较），然后把这个数加1……

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/27 13:17:00
     
     dyctomato 帅哥哟，离线，有人找我吗？
      
      等级：大一新生
      文章：4
      积分：73
      门派：XML.ORG.CN
      注册：2006/4/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给dyctomato发送一个短消息 把dyctomato加入好友 查看dyctomato的个人资料 搜索dyctomato在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看dyctomato的博客第3楼
    发贴心情 
    题目意思就是找出不在这1,000,000个数的最小的正整数
    有时间n空间1的算法
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/28 13:21:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第4楼
    发贴心情 
    一定要是最小的正整数吗？

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/28 13:30:00
     
     dyctomato 帅哥哟，离线，有人找我吗？
      
      等级：大一新生
      文章：4
      积分：73
      门派：XML.ORG.CN
      注册：2006/4/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给dyctomato发送一个短消息 把dyctomato加入好友 查看dyctomato的个人资料 搜索dyctomato在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看dyctomato的博客第5楼
    发贴心情 
    不一定要最小
    只要在1～size里找个没有的就行，反正找最小的也不会需要更多的时间或空间

    你的方法要是MAXINT在那些非负整数里怎么办？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/29 21:38:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第6楼
    发贴心情 
    MAXINT在那些非负整数里没关系，因为我取的是“MAXINT+1”……

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/30 17:41:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第7楼
    发贴心情 
    不过我想不出能在O(N)时间O(1)空间能找出最小的不在数组里的编号的方法。
    能说说你的办法吗？

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/1 15:45:00
     
     GoogleAdSense天蝎座1984-10-28
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Google AdSense  访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/28 8:01:08

    本主题贴数7，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 93.750ms