posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          水源上看到的騰訊筆試題

          Posted on 2007-04-26 12:37 ZelluX 閱讀(4538) 評論(3)  編輯  收藏 所屬分類: Algorithm

          發信人: anchorzhao (anchor), 信區: Algorithm
          標  題: 請教騰訊筆試題
          發信站: 飲水思源 (2007年04月23日13:01:40 星期一)

          只有2G內存的pc機,在一個存有10G個整數的文件,從中找到中位數,寫一個算法。
          --

          ※ 來源:·飲水思源 bbs.sjtu.edu.cn·[FROM: 202.120.37.193]


          發信人: xreborner (xreborner), 信區: Algorithm
          標  題: Re: 請教騰訊筆試題
          發信站: 飲水思源 (2007年04月24日11:23:07 星期二), 轉信

          ……
          一個整數假設是32位無符號數
          第一次掃描把0~2^32-1分成2^16個區間,記錄每個區間的整數數目
          找出中位數具體所在區間65536*i~65536*(i+1)-1
          第二次掃描則可找出具體中位數數值

          【 在 howe (無痕) 的大作中提到: 】
          : 這小子吹牛
          : 【 在 acmboy (雪狼,想創業,人不霸王枉少年) 的大作中提到: 】
          : : 這小子夠壞的,居然不說怎么做~~~


          --
          心碼合一,心中有代碼,碼中存我心;維碼無心,心動即碼動,代碼表我心;
          維心無碼,視萬物皆空,知萬千變化;無碼無心,行如若無規,動全依所意。

          ※ 來源:·飲水思源 bbs.sjtu.edu.cn·[FROM: 202.120.224.18]

          發信人: xreborner (xreborner), 信區: Algorithm
          標  題: Re: 請教騰訊筆試題
          發信站: 飲水思源 (2007年04月24日18:37:01 星期二), 轉信

          可以保證的
          因為第一次掃描已經找出中位數具體所在區間65536*i~65536*(i+1)-1
          然后第二次掃描再統計在該區間內每個數出現的次數
          就可以了
          實在是太簡單了

          【 在 acmboy (雪狼,想創業,人不霸王枉少年) 的大作中提到: 】
          : anyway,good solution ,雖然不能保證兩次完成
          : 【 在 acmboy (雪狼,想創業,人不霸王枉少年) 的大作中提到: 】
          : : 如果int[] 是不重復的話可以的,
          : : 如果在中位數附近重復的比較厲害的話,呵呵


          評論

          # re: 水源上看到的騰訊筆試題  回復  更多評論   

          2008-07-15 16:45 by 不說
          恩。想法不錯啊

          # re: 水源上看到的騰訊筆試題  回復  更多評論   

          2008-07-15 16:46 by 不說
          但是內存利用率不高貌似

          # re: 水源上看到的騰訊筆試題  回復  更多評論   

          2009-05-30 22:23 by leesa
          恩 這個方法贊啊
          主站蜘蛛池模板: 神农架林区| 来宾市| 龙南县| 包头市| 江西省| 台东市| 防城港市| 葫芦岛市| 兰坪| 昌乐县| 横山县| 贺州市| 肇州县| 崇义县| 富顺县| 睢宁县| 莱阳市| 中方县| 方城县| 闵行区| 西丰县| 应用必备| 忻州市| 云龙县| 上高县| 环江| 赫章县| 新建县| 延长县| 吉安市| 弥渡县| 如东县| 稻城县| 嘉善县| 紫金县| 牟定县| 新和县| 阳东县| 阿图什市| 靖安县| 东乡县|