腾讯最新面试题,算法高手请进

converse

1.对两个集合排序之后再求交.
2.没看懂题目....

converse

两个都排序,分别要LOG(N)吧,然后一边扫描就可以求出交集了,是O(N),所以时间复杂度是O(N).

nopeno

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

nopeno

第二题的方法
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 就是你要的