我有一个由'n'个元素组成的unordered_map。它有一些合格的元素。我想写一个函数,每次都随机挑选一个合格的元素。这能在下面的时间复杂度内实现吗?最好的情况是:O(1)平均情况:O(1)最差情况:时间复杂度O(n)
在C++中引用- retrieve random key元素为std::map时,我想出了下面的解决办法。
#include <iostream>
#include <unordered_map>
#include <random>
using namespace std;
void select_random_best(const std::unordered_map<std::string, int>& umap, const int random_start)
{
cout << "Selected random number " << random_start << endl;
auto it = umap.begin();
std::advance(it, random_start);
for(int i = 0; i < umap.size(); i++, it++) {
if(it == umap.end())
it = umap.begin();
// Check if the selected element satisfies the eligibility criteria.
// For the sake of simplicity, I am taking the following example.
if(it->second % 3 == 0) {
cout << it->first << ", " <<
it->second << endl;
return;
}
// Element not found continue searching
}
}
int main()
{
srand(time(0));
unordered_map<string, int> umap;
// inserting values by using [] operator
umap["a"] = 6;
umap["b"] = 3;
umap["f"] = 9;
umap["c"] = 2;
umap["d"] = 1;
umap["e"] = 3;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distrib(0, umap.size() - 1);
const int random_start = distrib(gen);
select_random_best(umap, distrib(gen));
// another iteration
select_random_best(umap, distrib(gen));
cout << "Full list :" << endl;
// Traversing an unordered map
for (auto x : umap)
cout << x.first << ", " <<
x.second << "\t";
}
如果在这里使用std::advance()
会导致平均时间复杂度为O(1),有没有更好的方法?
1条答案
按热度按时间cngwdvgl1#
std::unordered_map
具有不允许随机访问的前向迭代器。请参阅有关the documentation page of the container的iterator
。假设所有要素均合格,则
std::advance()
平均将搜索size/2
个要素。由于您只接受合格要素,因此将搜索更多要素。如果您知道合格概率,则可以估计搜索的平均要素。在
std::advance()
步骤中,要达到O(1),必须使用带有随机访问迭代器的数据类型,例如std::vector
。然而,下一步没有恒定的复杂度。在最坏的情况下,您将遍历所有不合格的元素(如果没有合格的元素,则不考虑无限循环的可能性)。因此,这种方法总体上仍然是O(n)。为了获得最佳性能,您需要两个列表:
std::vector
仅具有合格的元素,用于查找随机元素,而std::unordered_map
用于其他内容。