C,快速从另一个向量唯一的向量中删除元素
发布时间：2020-12-16 09:40:02 所属栏目：百科 来源：网络整理
导读：有两个int的未分类向量和对int,int的向量 std::vector int v1;std::vector std::pairint,float v2; 包含数百万件物品. 如何尽可能快地从v1中删除这些v2.first独有的项目(即不包含在v2.first中)？ 例： v1: 5 3 2 4 7 8v2: {2,8} {7,10} {5,0} {8,9}---------
|
有两个int的未分类向量和对int,int的向量
std::vector <int> v1; std::vector <std::pair<int,float> > v2; 包含数百万件物品. 如何尽可能快地从v1中删除这些v2.first独有的项目(即不包含在v2.first中)？ 例： v1: 5 3 2 4 7 8
v2: {2,8} {7,10} {5,0} {8,9}
----------------------------
v1: 3 4
解决方法
我会尽快使用两种技巧来做到这一点：
>使用某种关联容器(可能是std :: unordered_set)来存储第二个向量中的所有整数,以便更有效地查找是否应该删除第一个向量中的某个整数. 更具体地说,我会做以下事情.首先创建一个std :: unordered_set,然后添加第二个向量中该对中第一个整数的所有整数.这给出了(预期的)O(1)查找时间来检查集合中是否存在特定的int. 既然你已经这样做了,使用std :: remove_if算法从哈希表中存在的原始向量中删除所有内容.您可以使用lambda来执行此操作： std::unordered_set<int> toRemove = /* ... */
v1.erase(std::remove_if(v1.begin(),v1.end(),[&toRemove] (int x) -> bool {
return toRemove.find(x) != toRemove.end();
},v1.end());
将所有内容存储在unordered_set中的第一步需要预期的O(n)时间.第二步通过将所有删除聚集到最后并使查找花费很少时间来完成预期的O(n)工作.这给出了整个过程的预期O(n) – 时间,O(n)空间的总和. 如果你被允许对第二个向量(对)进行排序,那么你也可以在O(n log n)最坏情况时间,O(log n)最坏情况空间中通过按键对向量进行排序,然后使用std :: binary_search检查是否应该删除第一个向量中的特定int.每个二进制搜索需要O(log n)时间,因此所需的总时间为排序的O(n log n),第一个向量中每个元素的O(log n)时间(总计为O(n log n)) )和O(n)删除时间,总共给出O(n log n). 希望这可以帮助！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |