unordered_map<int,int> mymap;
for(int i = 0; i < nums.size(); i++){
mymap[nums.at(i)]++;
}
priority_queue <pair<int,int>> maxheap;
for(auto it = mymap.begin(); it != mymap.end(); it++){
maxheap.push({it->second,it->first});
}
vector<int> result;
for(int i = 0; i < k; i++){
result.push_back(maxheap.top().second);
maxheap.pop();
}
return result;
我很困惑,因为在leetcode上,我循环并插入map的第一个for循环被计算为简单的O(n)时间。时间复杂度O(n^2)时间复杂度是O(n)的。
时间复杂度是O(n)的,所以我很困惑为什么第一个for循环的时间复杂度是O(n)
1条答案
按热度按时间gmxoilav1#
在内部,
unordered_map
是使用哈希表实现的,提供给Map的键被哈希到哈希表的索引中,这就是为什么数据结构的性能很大程度上取决于哈希函数,但平均而言,从哈希表中搜索,插入和删除的成本是O(1)
。