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
          恩 這個方法贊啊
          主站蜘蛛池模板: 科技| 上杭县| 陆川县| 西青区| 方正县| 绿春县| 吉安市| 安西县| 遂昌县| 宁津县| 玛曲县| 铜山县| 鲁山县| 平武县| 贡山| 宣化县| 阿巴嘎旗| 德昌县| 洱源县| 贡觉县| 武陟县| 东山县| 乐清市| 临汾市| 台北市| 新和县| 宁乡县| 祁门县| 叶城县| 泗水县| 德惠市| 高台县| 方城县| 同仁县| 济宁市| 广平县| 淄博市| 韶关市| 乌鲁木齐市| 大田县| 永兴县|