那么时间复杂度就是从读取,容器内数据的查找,删除,插入两大步骤来算,读取的时间复杂度是n,如果我们使用树结构来做容器,那么容器内的操作时间复杂度就是lg(k), 因此总的时间复杂度就是nlg(k)。要剔除最大的数,我们自然而然想到最大堆。当然我们也可以用红黑树来做,直接就可以使用STL里面的set数据集合。由于是海量的数据,而内存的空间又是有限的,我们需要借助辅助内存来存储数据,可以使用磁盘什么的。大概分析到这里了。
源码:
// ====================方法2====================
typedef multiset<int, std::greater<int> > intSet;
typedef multiset<int, std::greater<int> >::iterator setIterator;
void GetLeastNumbers_Solution2(const vector<int>& data, intSet& leastNumbers, int k)
{
leastNumbers.clear();
if(k < 1 || data.size() < k)
return;
vector<int>::const_iterator iter = data.begin();
for(; iter != data.end(); ++ iter)
{
if((leastNumbers.size()) < k)
leastNumbers.insert(*iter);
else
{
setIterator iterGreatest = leastNumbers.begin();
if(*iter < *(leastNumbers.begin()))
{
leastNumbers.erase(iterGreatest);
leastNumbers.insert(*iter);
}
}
}
}