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
          恩 這個方法贊啊
          主站蜘蛛池模板: 仲巴县| 西宁市| 全南县| 汾阳市| 梁山县| 江城| 尉犁县| 柯坪县| 滁州市| 炉霍县| 潜山县| 庆城县| 三江| 文成县| 衡阳市| 华蓥市| 富蕴县| 鄱阳县| 厦门市| 株洲市| 惠州市| 潮州市| 凯里市| 榆中县| 军事| 个旧市| 永康市| 石河子市| 哈尔滨市| 怀仁县| 南涧| 金堂县| 巴彦淖尔市| 乐至县| 翁源县| 天气| 肇庆市| 凌海市| 宝兴县| 德令哈市| 枣庄市|