From this https://stackoverflow.com/questions/2400157/the-intersection-of-two-sorted-arrays,我们知道解决两个排序数组的交集的方法。那么如何获取多个已排序数组的交集呢?
根据两个排序数组的答案,我们可以将其应用于多个数组。这是代码
vector<int> intersectionVector(vector<vector<int> > vectors){
int vec_num = vectors.size();
vector<int> vec_pos(vec_num);// hold the current position for every vector
vector<int> inter_vec; // collection of intersection elements
while (true){
int max_val = INT_MIN;
for (int index = 0; index < vec_num; ++index){
// reach the end of one array, return the intersection collection
if (vec_pos[index] == vectors[index].size()){
return inter_vec;
}
max_val = max(max_val, vectors[index].at(vec_pos[index]));
}
bool bsame = true;
for (int index = 0; index < vec_num; ++index){
while (vectors[index].at(vec_pos[index]) < max_val){
vec_pos[index]++; // advance the position of vector, once less than max value
bsame = false;
}
}
// find same element in all vectors
if (bsame){
inter_vec.push_back(vectors[0].at(vec_pos[0]));
// advance the position of all vectors
for (int index = 0; index < vec_num; ++index){
vec_pos[index]++;
}
}
}
}
有没有更好的方法来解决呢?
Update1
从这两个话题1 https://stackoverflow.com/questions/497338/efficient-list-intersection-algorithm and 2 https://stackoverflow.com/questions/4642172/computing-set-intersection-in-linear-time,看来Hash set
是更有效的方法。
Update2
为了提高性能,也许min-heap
可以用来代替vec_pos
在我上面的代码中。和变量max_val
保存所有向量的当前最大值。所以只需将根值与max_val
,如果相同,则可以将该元素放入交集列表中。
要获得两个排序范围的交集,std::set_intersection http://en.cppreference.com/w/cpp/algorithm/set_intersection可以使用:
std::vector<int> intersection (const std::vector<std::vector<int>> &vecs) {
auto last_intersection = vecs[0];
std::vector<int> curr_intersection;
for (std::size_t i = 1; i < vecs.size(); ++i) {
std::set_intersection(last_intersection.begin(), last_intersection.end(),
vecs[i].begin(), vecs[i].end(),
std::back_inserter(curr_intersection));
std::swap(last_intersection, curr_intersection);
curr_intersection.clear();
}
return last_intersection;
}
这看起来比您的解决方案干净得多,您的解决方案太混乱而无法检查正确性。
它还具有最佳的复杂性。
标准库算法set_intersection
可以以任何使用的方式实现
最多 2·(N1+N2-1) 次比较,其中 N1 = std::distance(first1, last1) 且 N2 = std::distance(first2, last2)。
first1
等等是定义输入范围的迭代器。如果标准库是开源的(例如 libstd++ 或 libc++),您可以在其源代码中查看实际实现。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)