cc

对于第二个题目写了个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;
}
}
测试的话可以手动或用脚本生成日志文件
~>awk -f luntan logfile
or
~>echo 2 20 |awk -f luntan   回复  更多评论
  

我表达的不太清晰,一天有24*3600秒
每个ID在日志中的数据格式如下:12 200 即该用户在今天的第12秒到200秒在线
日志文件中大概有2亿个这种记录,问题是求在一天中的第N 秒的在先人数   回复  更多评论
  

对于求交集的问题,我的算法是:
假设
A 元素个数为 NA
B 元素个数为 NB
NA > NB
对集合B快速排序,然后遍历集合A的元素在集合B中用2分查找
复杂度:NB*log(NB) + NA*log(NB)
如果两个都排序,光排序的时间就大于这个了   回复  更多评论
  

第二题的方法
int delta[86400]; //定义每秒钟人数的变化数
memset(delta, 0, sizeof(delta)); //初始化
//打开文件
while(!feof(....)){
int online_tm, int offline_tm; //
//读入上线时间和下限时间
delta[online_tm]++;
delta[offline_tm]--;
}
int result[86400];
int begin_total; //0:00的在线数，需要初始化
int totla = begin_total;
for(int i = 0; i < 86400; i++){
result[i] = total;
total += delta[i];
}

//到这儿result 就是你要的  回复  更多评论
  

第一题的方法，这不是一个好办法，无非是一个解决办法而已
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;
}   回复  更多评论
  

A+B快排,然后遍历  回复  更多评论
  

1.hash不行吗  回复  更多评论