我使用载体向量来存储id数字,我想比较所有这些元素并删除其中的所有值已经在另一个元素内的元素。比较载体和删除载体,其中所有元素已经在另一个载体内
说我在我的矢量4个元素这样
[[1,2,3,4],[1,2,3],[3],[1,2,3,5] ]
在这个例子中,第二个和第三个元素应该被删除。
什么是最快的算法来解决这个问题?
我使用载体向量来存储id数字,我想比较所有这些元素并删除其中的所有值已经在另一个元素内的元素。比较载体和删除载体,其中所有元素已经在另一个载体内
说我在我的矢量4个元素这样
[[1,2,3,4],[1,2,3],[3],[1,2,3,5] ]
在这个例子中,第二个和第三个元素应该被删除。
什么是最快的算法来解决这个问题?
以下是一种可能的解决方案。
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
typedef std::vector<int> VI;
typedef std::vector<std::vector<int>> VVI;
VVI DeleteDups(VVI vvi) {
std::map<int,int> map;
for(auto const& vi : vvi)
for(auto const& i : vi)
++map[i];
vvi.erase(
std::remove_if(begin(vvi), end(vvi),
[&map](const VI& vi)->bool {
for(int i : vi)
if(map[i] == 1) return false;
return true;
}),
end(vvi));
return vvi;
}
void Dump(const VVI& vvi) {
std::cout << "[";
for(auto const& vi : vvi) {
std::cout << "[";
for(int i : vi)
std::cout << i << ", ";
std::cout << "], ";
}
std::cout << "]\n";
}
int main() {
Dump(DeleteDups({ {1,2,3,4}, {1,2,3}, {3}, {1,2,3,5} }));
}
std :: unordered_map应该比std :: map更快。 –
“里面的所有值已经*在另一个元素内*”。即要求不是“唯一性”,而是“不包括\t 包含” –
重新:唯一性。同意。但对于给出的样本数据,“不在另一个元素内”和“独特”是相同的。 –
这里满足“已经在另一个元素内”的解决方案需求,而不仅仅是元素的“唯一性”。
对于[[1,2,3,4],[1,2,3],[3],[1,2,3,5]],输出为[[1,2,3,4 ],[1,2,3,5]]。
对于[[1,2,3,4],[1,2,3],[3,4],[1,2,3,5]],输出为[[1,2,3] ,4],[1,2,3,5]]。
它的工作原理如下:
#include <boost/container/vector.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/assign/list_of.hpp>
#include <boost/unordered_map.hpp>
#include <boost/foreach.hpp>
#include <iterator>
#include <iostream>
#include <ostream>
#include <cstddef>
#include <string>
using namespace boost::assign;
using namespace boost;
using namespace std;
template<typename VecVec,typename OutputIterator>
void delete_included(const VecVec &vv,OutputIterator out)
{
typedef typename range_value<VecVec>::type vec_type;
typedef typename const vec_type *vec_id;
typedef typename range_value<vec_type>::type value_type;
unordered_map<value_type,container::vector<vec_id> > value_in;
container::vector<vec_id> all_vec_indexes;
BOOST_FOREACH(const vec_type &vec,vv)
{
all_vec_indexes.push_back(&vec);
BOOST_FOREACH(const value_type &value,vec)
{
value_in[value].push_back(&vec);
}
}
container::vector<vec_id> included_in;
container::vector<vec_id> intersect;
BOOST_FOREACH(const vec_type &vec,vv)
{
included_in=all_vec_indexes;
BOOST_FOREACH(const value_type &value,vec)
{
intersect.clear();
set_intersection(included_in,value_in[value],back_inserter(intersect));
swap(included_in,intersect);
if(included_in.size()==1)
break;
}
if(included_in.size()==1)
{
*out=vec;
++out;
}
}
}
template<typename VecVec>
void print(const VecVec &vv)
{
typedef typename range_value<VecVec>::type vec_type;
typedef typename range_value<vec_type>::type value_type;
cout << string(16,'_') << endl;
BOOST_FOREACH(const vec_type &vec,vv)
{
copy(vec,ostream_iterator<const value_type&>(cout," "));
cout << endl;
}
}
int main(int argc,char *argv[])
{
container::vector<container::vector<int> > vv
(list_of
(list_of (1)(2)(3)(4))
(list_of (1)(2)(3))
(list_of (3))
(list_of (1)(2)(3)(5))
);
print(vv);
container::vector<container::vector<int> > result;
delete_included(vv,back_inserter(result));
print(result);
return 0;
}
我会建议你做自己的研究,并表现出一定的努力。 –
你想彻底摆脱重复?如果是的话,一种插入所有载体的集合可能是有意义的。 – Xeo
好吧,我认为你的问题太过于开放式结束了,但为了给你一个帮助,std :: remove和std :: vector :: erase将会成为你std :: set_intersect和std :: back_inserter的朋友。如果您获得解决方案并需要帮助,我们可能会提供更多帮助。 – 111111