"x"的所有元素都存在于"y"(排序向量)中吗?

Question

设x和y是两个排序向量。我想弄清楚三者中哪一个是正确的

A. All elements of `y` are present in `x`
B. Some but not all elements of `y` are present in `x`
C. No element of `y` is present in `x`
U. Undefined (because `y` is empty)

实现这一目标的一种天真方法是

template<typename T>
char f(std::vector<T> x, std::vector<T> y)
{
if (y.size() == 0)
{
return 'U';
}
bool whereAnyElementFound = false;
bool whereAnyElementNotFound = false;
for (T& y_element : y)
{
bool isElementFound = std::find(x.begin(),x.end(),y_element) != x.end();
if (isElementFound)
{
whereAnyElementFound = true;
if (whereAnyElementNotFound)
{
return 'B';
}
} else
{
whereAnyElementNotFound = true;
if (whereAnyElementFound)
{
return 'B';
}
}
}
if (whereAnyElementFound)
{
return 'A';
} else if (whereAnyElementNotFound)
{
return 'C';
}
abort();
}

该函数将以下输入与输出正确匹配

inputs: x = {1,2,4,5} y = {2,5}
output: A
inputs: x = {1,2,4,5} y = {2,7}
output: B
inputs: x = {1,2,4,5} y = {6,7}
output: C
inputs: x = {1,2,4,5} y = {}
output: U

但是，此方法没有利用两个向量都排序的事实。对于较大的向量，如何使此功能更快？

Answer 1

对于O(N)额外空间的成本，您可以使用std::set_intersection. 它具有O(2(N1+N2-1))复杂性，并在两个向量之间生成所有公共元素的"集合"。 然后，您可以检查新"集合"的大小以找出 A、B、C 和 U。

int main()
{
std::vector<int> v1{1,2,3,4,5,6,7,8};
std::vector<int> v2{5,7,9,10};
std::vector<int> intersection;
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(intersection));
if (intersection.size() == v2.size() && v2.size() > 0)
std::cout << "A";
else if (intersection.size() > 0)
std::cout << "B";
else if (intersection.size() == 0 && v2.size() > 0)
std::cout << "C";
else
std::cout << "U";
}