Возвращение индекса в подмассиве на основе делимости на другое число

Question

Я пытаюсь вернуть индекс в подмассив, до которого все элементы в подмассиве делятся на некоторое большое число K (тип long long).Мне удалось написать правильный код, но сложность не велика.Кто-нибудь может предложить лучший способ сделать это для оптимизации времени выполнения?

long long solve (vector<long long> A, long long K, int R, int L) {

       int index=L-1;
       int count=0;
       while(A[index]%K==0 && index<=R-1){
           if(A[index]%K==0){
               count++;
           }
           index++;
       }
        if(count!=0){
            return (L+count-1);
        }
        else{
            return -1;
        }
}

Здесь параметры следующие: L - крайняя левая граница подмассива R - крайняя правая граница подмассива A - вектор, содержащий всюмассив.A = {1,2,4,5,7,9}

Например, если я передам L=2, R=4, K=2, он вернет index=3 (индексы начинаются с 1).Другими словами, от индекса 1 до 3 в векторе, который мы проверяем, от L до R, какой бы элемент не делился на K.Мы идем вперед до тех пор, пока элемент в этой последовательности не будет соответствовать критериям делимости.Затем мы печатаем его конечный индекс.В противном случае, если ни один такой элемент не удовлетворяет критериям, мы возвращаем -1

Answer 1

Это очень плохой дизайн функции, который не соответствует концепции C ++.

Для индексов начинающих в C ++ начинается с 0. Во-вторых, диапазон указывается как [start, end), то есть end не входит в диапазон.

Функция должна возвращать объект типа std::vector<long long>::size_type. Если элемент, удовлетворяющий условию, не найден в диапазоне, функция должна вернуть значение end.

Я бы написал функцию следующим образом, как показано в демонстрационной программе

#include <iostream>
#include <vector>
#include <algorithm>

auto solve( const std::vector<long long> &v, 
            std::vector<long long>::size_type first,
            std::vector<long long>::size_type last,
            long long value )
{
    last  = std::min( last, v.size() );
    first = std::min( first, last );

    auto current = first;

    while ( ( current != last ) && ( v[current] % value == 0 ) ) ++current;

    return current == first ? last : current - 1;
}

int main()
{
    using size_type = std::vector<long long>::size_type;

    std::vector<long long> v = { 1, 2, 4, 5, 7, 9 };

    size_type first   = 1;
    size_type last    = 3;
    long long divisor = 2;

    auto i = solve( v, first, last, divisor );

    if ( i != last )
    {
        std::cout << "The last element divisible by " << divisor
                  << " in the range [" << first
                  << ", " << last
                  << ") is at position " << i << '\n';
    }
    else
    {
        std::cout << "There is no element divisible by " << divisor 
                  << " in the range [" << first 
                  << ", " << last << ")\n";
    }
}

Его вывод

The last element divisible by 2 in the range [1, 3) is at position 2

Вы можете написать ту же функцию, используя итераторы. В этом случае объявление функции будет выглядеть проще.

Например

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

auto solve( std::vector<long long>::const_iterator first, 
            std::vector<long long>::const_iterator last,
            long long value )
{
    auto it = std::find_if_not( first, last, 
                                [&value]( const long long &item ) { return item % value != 0; } );

    return it == first ? last : std::prev( first );
}

int main()
{
    std::vector<long long> v = { 1, 2, 4, 5, 7, 9 };

    auto first = std::next( std::cbegin( v ), 1 );
    auto last  = std::next( std::cbegin( v ), 3 );
    long long divisor = 2;

    auto it = solve( first, last, divisor );

    if ( it != last )
    {
        std::cout << "The last element divisible by " << divisor
                  << " in the range [" << std::distance( std::cbegin( v ), first )
                  << ", " << std::distance( std::cbegin( v ), last )
                  << ") is at position " << std::distance( std::cbegin( v ), it ) << '\n';
    }
    else
    {
        std::cout << "There is no element divisible by " << divisor 
                  << " in the range [" << std::distance( std::cbegin( v ), first ) 
                  << ", " << std::distance( std::cbegin( v ), last ) << ")\n";
    }
}

Answer 2

Ваша логика ошибочна, так как она не выходит из цикла в другом случае.Вместо того, чтобы работать над исправлением, которое я бы предложил перейти к использованию стандартных алгоритмов, а не писать свои собственные, например:

const auto start = next(cbegin(A), L - 1);
const long long finish = distance(start, find_if(start, next(cbegin(A), R - 1), bind(modulus<int>(), placeholders::_1, K)));
const auto result = finish == 0 ? -1 : finish;

Как и , упомянутое Владом из Москвы ваш 1-ориентированныйиндексация увеличивает сложность.Если вы готовы использовать индексирование на основе 0, перейдите к возврату 0 вместо -1 и используйте лямбду, которую вы можете просто сделать:

const auto result = count_if(next(cbegin(A), L), next(cbegin(A), R), [=](const auto i) { return i % K == 0; })