考虑 map mymap 有条目
<'a', 111>
<'b', 567>
<'c', 956>
<'d', 222>
<'e', 111>
<'f', 222>
<'h', 222>
<'i', 492>
等等...
如何删除 map 中重复值的条目。
例如键“a”和“e”存在值 111。所以保留 'a' 的映射条目并删除 'e' 的条目
对于值 222,保留条目“d”并删除条目“f”和“h”。
我正在寻找具有最佳空间和时间复杂度的解决方案
这是一个有趣的问题,即使有点偏离主题。
因为你的 map 的值是可散列的和相等的可比性,那么我们可以在线性时间内做到这一点,使用 unordered_set
来确定该值是否已经被看到过:
此代码为 c++17:
void comb(std::map<char, int>& themap)
{
std::unordered_set<int> seen;
seen.reserve(themap.size());
// iterate through the map in key order...
auto current = begin(themap);
const auto last = end(themap);
while(current != last)
{
auto&&[key, value] = *current;
// try to insert the value into the 'seen' set.
if (seen.insert(value).second)
// if we succeeded, then we're the first ocurrence of the
// value so move to next node
++current;
else
// otherwise, erase this node and move to the next
// (idiomatic method)
current = themap.erase(current);
}
}