• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            life02

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              197 隨筆 :: 3 文章 :: 37 評論 :: 0 Trackbacks

            2009.9.12日下午 迅雷2筆試題

            有一副牌編號0~51,請把這副牌盡可能隨機的發到4個人手里
            注1:已經有rand()函數可以調用,但是rand()函數開銷較大,請盡量少調用

            a,b,c,d分別是13個元素的1維數組
            函數原型 void deal( int[] a, int[] b, int[] c, int[] d );


            實現字符串反轉的c庫函數 char* strrev(char* string)
            注1:不可利用其他庫函數,算法盡量高效、占用空間少。


            有10億個數,這些數的值都在0~1000萬之內。實現接口 get_bigger_count( unsigned value )
            輸入一個值value,返回這10億個數中比value值大的數的數目。
            class order_calculate
            {
            public:
            order_calculate();
            ~order_calculate();
            unsinged get_bigger_count( unsigned value )
            }
            注1:get_bigger_count接口會被頻繁的調用,實現要高效
            注2:可以自己往內部任意添加變量和接口
            注3:有個現成的接口 unsigned get_value_by_index( int idx ) 可以調用,該接口返回指定索引的value值
                 比如 get_value_by_index( 100 ), 返回10億個數中第100個數的值。該接口開銷較大,盡量少調用。



            http://topic.csdn.net/u/20090912/20/8c60e06e-321c-49a6-b2cc-59248ba9cf36.html?28642 

            posted on 2009-09-13 16:29 life02 閱讀(781) 評論(2)  編輯 收藏 引用 所屬分類: 筆試

            評論

            # re: 筆試題 2009-09-14 18:16 life02
            第三題正解如下:
            這題很明顯已經告訴各位了,算法復雜度是o(1),任何其他排序算法都是錯的,只有桶排序可行,原因也很明顯,符合桶排序的特征,0到1000萬的取值范圍已經固定了,相對10億來說1000萬是很小了。

            所以只要設立0到1000萬的桶,中間附加計數即可,什么意思呢,10億個數據,如果縮小一點:范圍是0到10的話
            0,1,2,3,4,5,6,7,8,9,10

            在每一個桶下面掛一個count,掃描完后,10億個數據肯定都在這10個桶里(1000萬類似)

            這樣在接下來查詢的時候,其實比較空間只有0到1000萬,和10億一點關系都沒有,而且每個桶還幫你記著大于該數的個數,所以假定要比較的數值是5,則結果就是5,6,7,8,9,10的count之和。

            計算空間最大浪費就是在0到1000萬里面,找到你的那個數值,但是總比N要小很多,這個結論拿出去,面試來說,應該可以得滿分,至于效率,空間什么的,就自己優化1000萬數據的比較算法啦。  回復  更多評論
              

            # re: 筆試題 2009-09-18 10:09 life02
            #include <iostream>
            #include <stdio.h>
            #include <assert.h>
            using namespace std;


            static unsigned int *pindex;

            #define L 10000001
            unsigned get_bigger_count(unsigned value)
            {
            assert(value<L-1);
            static binit(false);
            unsigned int rval(0);
            if(!binit)
            {
            FILE *fp = fopen("datafile", "r+b");
            unsigned int i = 0;
            unsigned int shu;
            pindex = new unsigned int[L];
            memset(pindex, 0, sizeof(unsigned int)*L);

            while(fscanf(fp,"%ld",&shu)!=-1){
            /* cout<<shu<<endl;*/
            pindex[shu]++;
            }
            fclose(fp);
            for(i=L-1; i>0; --i)
            pindex[i-1] += pindex[i];
            }
            binit = true;
            rval = pindex[value+1];
            return rval;
            }




            int main(){
            unsigned un;
            un=get_bigger_count(8738787);
            cout<<un<<endl;
            return 0;
            }  回復  更多評論
              

            一本色综合久久| 国产精品久久成人影院| 久久久中文字幕| 777米奇久久最新地址| 精品久久久久久久久午夜福利| 久久精品桃花综合| 亚洲色大成网站www久久九| 日本人妻丰满熟妇久久久久久| 久久亚洲sm情趣捆绑调教| 99久久免费国产精品特黄| 国产成人无码精品久久久性色 | 久久精品成人免费国产片小草| 色噜噜狠狠先锋影音久久| 久久AAAA片一区二区| 2021国内久久精品| 久久国产精品久久| 久久婷婷是五月综合色狠狠| 久久无码人妻一区二区三区| 国产69精品久久久久777| 久久国产成人精品国产成人亚洲| 久久久久免费精品国产| 久久综合丁香激情久久| 日韩va亚洲va欧美va久久| 人妻久久久一区二区三区| 国产精品久久久久久久久久免费| 亚洲精品无码专区久久同性男| 久久无码人妻一区二区三区午夜| 久久精品国产一区二区三区| 无码人妻久久一区二区三区免费| 无码国内精品久久人妻麻豆按摩| 狠狠色丁香久久婷婷综合五月| 一级a性色生活片久久无| 9999国产精品欧美久久久久久| 中文字幕久久精品| 久久久91人妻无码精品蜜桃HD| 99久久99久久精品免费看蜜桃| 久久只有这里有精品4| 久久久精品国产亚洲成人满18免费网站 | 久久国产乱子伦免费精品| 色偷偷91久久综合噜噜噜噜| 国产精品热久久无码av|