проверить, может ли один вектор <int>быть вложенным в другой

Question

Я испытываю проблемы с Edabit, и текущая задача связана с вложением векторов. инструкции: Создайте функцию, которая возвращает true, если первый массив может быть вложен во второй.

Массив 1 может быть вложен в массив 2, если:

1. Массив 1 мин.> Массив 2 мин.
2. Максимум массива 1 <Максимум массива 2 </li>

Примеры:

canNest([1, 2, 3, 4], [0, 6]) ➞ true

canNest([3, 1], [4, 0]) ➞ true

canNest([9, 9, 8], [8, 9]) ➞ false

canNest([1, 2, 3, 4], [2, 3]) ➞ false

код, который я написал, который не проходит все тесты, следующий:

bool canNest(std::vector<int> arr1, std::vector<int> arr2) {
    return (std::min_element(arr1.begin(), arr1.end()) > 
                 std::min_element(arr2.begin(), arr2.end()) && 
                 std::max_element(arr1.begin(), arr1.end()) < 
                 std::max_element(arr2.begin(), arr2.end()));
}

Этот код выполняет тесты test3, test4 и test5, но не для test1 и test2.

    It(test1){Assert::That(canNest({1, 2, 3, 4}, {0, 6}), Equals(true));}
    It(test2){Assert::That(canNest({3, 1}, {4, 0}), Equals(true));}
    It(test3){Assert::That(canNest({9, 9, 8}, {8, 9, 10}), Equals(false));}
    It(test4){Assert::That(canNest({9, 9, 8}, {8, 9}), Equals(false));}
    It(test5){Assert::That(canNest({1, 2, 3, 4}, {2, 3}), Equals(false));}

РЕДАКТИРОВАТЬ: задачу можно найти здесь , для тестирования решения!

Answer 1

Как уже упоминалось в комментариях, используемые вами алгоритмы возвращают итераторы, на которые нужно ссылаться.Для этой задачи вам, вероятно, следует взглянуть на их компаньона std::minmax_element, который возвращает итераторы как элементу min, так и max, чтобы не приходилось многократно просматривать списки:

bool canNest(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    auto [min1, max1] = std::minmax_element(arr1.begin(), arr1.end());
    auto [min2, max2] = std::minmax_element(arr2.begin(), arr2.end());

    return *min1 > *min2 && *max1 < *max2;
}

Альтернативой является толькополучить min и max для вмещающего вектора и использовать алгоритм, который вернет false раньше, если не будет выполнено общее условие.Это может быть более эффективным, особенно для больших наборов данных.

bool canNestImproved(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    auto [min2it, max2it] = std::minmax_element(arr2.begin(), arr2.end());

    // all elements in arr1 must fall within the boundaries and std::all_of
    // will stop iterating over arr1 as soon as the lambda returns false.
    return std::all_of(
        arr1.begin(), arr1.end(),
        [min2 = *min2it, max2 = *max2it](int x) { return x > min2 && x < max2; });
}

Answer 2

как сказал Дюха в комментариях, min / max_element возвращает итератор, и вам нужно разыменовать его.

bool canNest(std::vector<int> arr1, std::vector<int> arr2) {
    return (*std::min_element(arr1.begin(), arr1.end()) > 
                 *std::min_element(arr2.begin(), arr2.end()) && 
                 *std::max_element(arr1.begin(), arr1.end()) < 
                 *std::max_element(arr2.begin(), arr2.end()));
}