按键相交两张地图的最有效方法是什么?
例如:给定
map<int, float> m1;
map<int, float> m2;
m1[1] = 1.0;
m1[2] = 4.0;
m1[3] = 3.0;
m1[7] = 5.0;
m2[7] = 3.0;
m2[4] = 2.0;
m2[2] = 4.0;
m2[9] = 6.0;
我需要一个vector<int>
与交集的结果!
预期结果将是:2
和7
按键相交两张地图的最有效方法是什么?
例如:给定
map<int, float> m1;
map<int, float> m2;
m1[1] = 1.0;
m1[2] = 4.0;
m1[3] = 3.0;
m1[7] = 5.0;
m2[7] = 3.0;
m2[4] = 2.0;
m2[2] = 4.0;
m2[9] = 6.0;
我需要一个vector<int>
与交集的结果!
预期结果将是:2
和7
由于键是排序的,这很容易在 O(n) 时间内完成。只需遍历它们中的每一个,只要键相等,就将该键添加到向量并递增两个迭代器。否则递增具有最低键的迭代器。
答案与设置交集相同。循环遍历第一组,并查询该元素是否在第二组中。复杂度为 O(n lg m),而 n 和 m 分别是 2 个集合的大小。
如果您使用由哈希表而不是红黑树支持的 unordered_map,您可以获得复杂度为 O(n)。
我可以认为这是m1
并且m2
已经有排序的元素在得到一个向量O(n)
std::vector<int> v_intersection;
map<int, float> ::iterator i,j;
i=m1.begin(),j=m2.begin();
for(; i!=m1.end() && j!=m2.end() ;)
if (i->first < j->first)
++i;
else if (i->first > j->first)
++j;
else{
v_intersection.push_back(i->first);
++i,++j;
}
我为我的场景 修改了两张 STL 地图的交集。
template<typename keyType, typename leftValue, typename rightValue>
vector<keyType> intersectMaps(const map<keyType, leftValue>& left, const map<keyType, rightValue>& right) {
vector<keyType> result;
typename map<keyType, leftValue>::const_iterator itrL = left.begin();
typename map<keyType, rightValue>::const_iterator itrR = right.begin();
while (itrL != left.end() && itrR != right.end()) {
if (itrL->first < itrR->first) {
++itrL;
} else if (itrR->first < itrL->first) {
++itrR;
} else {
result.push_back(itrL->first);
++itrL;
++itrR;
}
}
return result;
}
例如。使用:
map<int, float> m1;
map<int, float> m2;
m1[1] = 1.0;
m1[2] = 4.0;
m1[3] = 3.0;
m1[7] = 5.0;
m2[7] = 3.0;
m2[4] = 2.0;
m2[2] = 4.0;
m2[9] = 6.0;
vector<int> result = intersectMaps<int, float, float> (m1, m2);