Все ли элементы `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";
}