life02

三
有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 閱讀(804) 評論(2) 編輯收藏引用所屬分類: 筆試

第三題正解如下：
這題很明顯已經告訴各位了，算法復雜度是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;
} 回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: 字符轉int(轉) 鏈表反轉（轉）字符逆序（轉載） Activity的啟動模式（轉） Android筆試總結 (轉) 一個HR給應屆畢業生的面試建議后悔看到的太晚了（轉）群毆篇學習下，牛人的面試記錄（轉）東南融通筆試題（轉） 09騰訊筆試題（轉）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

life02

常用鏈接

留言簿(4)

隨筆分類(179)

隨筆檔案(197)

文章分類(1)

文章檔案(3)

收藏夾(16)

Android開發

c++blog——游戲

c++學習

QQblog

阿里巴巴

筆試

技術網站

游戲學習

搜索

最新評論

閱讀排行榜

評論排行榜

評論