c++ - 根据另一个数字的整除率返回子数组中的索引

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 是包含整个数组的 vector 。 A={1,2,4,5,7,9}

例如，如果我传递 L=2, R=4, K=2，那么它将返回 index=3(索引从 1 开始)。 换句话说，从 vector 中的索引 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";
    }
}