cc

對(duì)于第二個(gè)題目寫了個(gè)awk程序
~>cat luntan
#!/usr/bin/awk
{
a[$1]++;
a[$2 +1]--;
}
END{
s=0;
for(;i<=24*3600;i++)
{
s += a[i];
print "at second "i " total ID = " s;
}
}
測(cè)試的話可以手動(dòng)或用腳本生成日志文件
~>awk -f luntan logfile
or
~>echo 2 20 |awk -f luntan   回復(fù)  更多評(píng)論
  

我表達(dá)的不太清晰,一天有24*3600秒
每個(gè)ID在日志中的數(shù)據(jù)格式如下:12 200 即該用戶在今天的第12秒到200秒在線
日志文件中大概有2億個(gè)這種記錄,問題是求在一天中的第N 秒的在先人數(shù)   回復(fù)  更多評(píng)論
  

對(duì)于求交集的問題,我的算法是:
假設(shè)
A 元素個(gè)數(shù)為 NA
B 元素個(gè)數(shù)為 NB
NA > NB
對(duì)集合B快速排序,然后遍歷集合A的元素在集合B中用2分查找
復(fù)雜度:NB*log(NB) + NA*log(NB)
如果兩個(gè)都排序,光排序的時(shí)間就大于這個(gè)了   回復(fù)  更多評(píng)論
  

第二題的方法
int delta[86400]; //定義每秒鐘人數(shù)的變化數(shù)
memset(delta, 0, sizeof(delta)); //初始化
//打開文件
while(!feof(....)){
int online_tm, int offline_tm; //
//讀入上線時(shí)間和下限時(shí)間
delta[online_tm]++;
delta[offline_tm]--;
}
int result[86400];
int begin_total; //0:00的在線數(shù)，需要初始化
int totla = begin_total;
for(int i = 0; i < 86400; i++){
result[i] = total;
total += delta[i];
}

//到這兒result 就是你要的  回復(fù)  更多評(píng)論
  

第一題的方法，這不是一個(gè)好辦法，無非是一個(gè)解決辦法而已
std::list<int> unite(const std::list<int>& A, const std::list<int>& B)
{
std::map<int, bool> temp;
for(std::list<int>::const_iterator iter = A.begin(); iter != A.end(); iter ++){
if(temp.find(*iter) == temp.end()) temp[*iter] = true;
}
for(std::list<int>::const_iterator iter = B.begin(); iter != B.end(); iter ++){
if(temp.find(*iter) == temp.end()) temp[*iter] = true;
}
std::list<int> ret;
for(std::map<int, bool>::const_iterator iter = temp.begin(); iter != temp.end(); iter++){
ret.push_back(iter->first);
}
return ret;
}   回復(fù)  更多評(píng)論
  

A+B快排,然后遍歷  回復(fù)  更多評(píng)論
  

1.hash不行嗎  回復(fù)  更多評(píng)論