• <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 閱讀(783) 評論(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;
            }  回復  更多評論
              

            色诱久久av| 国内精品综合久久久40p| 日本久久久久久中文字幕| 久久久久久综合一区中文字幕| 岛国搬运www久久| 2021国产精品久久精品| 久久免费视频网站| 亚洲日本va午夜中文字幕久久| 亚洲精品乱码久久久久久久久久久久 | 亚洲国产成人久久综合野外| 一本色道久久综合狠狠躁| 久久青青草原综合伊人| 国内精品九九久久精品| 精品无码人妻久久久久久| 久久夜色精品国产噜噜噜亚洲AV| 久久亚洲国产精品一区二区| 777午夜精品久久av蜜臀| 国产精品美女久久久免费| 国产成人久久精品一区二区三区 | 色综合久久综合网观看| 精品熟女少妇AV免费久久| 久久人人爽人爽人人爽av| 国产精品女同久久久久电影院| 一本久久a久久精品综合香蕉| 亚洲国产精品一区二区久久| 亚洲AV成人无码久久精品老人| 久久成人18免费网站| 国产精品gz久久久| 色综合久久久久| 狠狠狠色丁香婷婷综合久久俺| 久久亚洲精品无码VA大香大香| 久久久久亚洲AV成人网人人网站| 久久美女网站免费| 久久免费精品视频| 91亚洲国产成人久久精品| 久久精品草草草| 久久美女人爽女人爽| 丰满少妇人妻久久久久久4| 精品久久久久中文字| 久久精品无码专区免费| 亚洲成av人片不卡无码久久|