C++

Question

给定一个未排序的向量和一个相同类型的输入元素，找到向量中小于给定元素的最大元素的最有效方法是什么？这是我目前所拥有的：

std::vector<double> vec{1,2.2,3.5,4};
double elem = 3;

double lessThan(double elem, std::vector<double> vec) 
{
    std::vector<double> tmp = vec;
    tmp.push_back(elem);
    sort(tmp.begin(), tmp.end());
    return *(find(tmp.begin(), tmp.end(), elem) - 1);
}

lessThan(elem, vec); //returns 2.2

谢谢

Answer 1

首先，不要按值传递向量，因为复制向量会导致传递值并写入内存，这既昂贵又不必要。

接下来，不要 sort() 元素：那既昂贵又不必要。只需进行线性搜索，记住迄今为止找到的最大合适值。您可能可以使用 max_element() 并将大于截止值的元素视为相等 class.

我可以写代码，但我不想破坏你解决家庭作业的乐趣。

Answer 2

最有效的方法是编写自己的函数。:)例如

#include <iostream>
#include <vector>

std::vector<double>::const_iterator lessThan( const std::vector<double> &v, 
                                              double value ) 
{
    auto first = v.begin();

    while ( first != v.end() && !( *first < value ) ) ++first;

    auto max = first;

    for ( ; first != v.end(); ++first )
    {
        if ( *first < value && *max < *first ) max = first;
    }

    return max;
}

int main() 
{
    std::vector<double> v = { 1, 2.2, 3.5, 4 };
    double value = 3.0;

    auto max = lessThan( v, value );

    if ( max != v.cend() )
    {
        std::cout << "The maximum value less than " << value
                  << " is " << *max << std::endl;
    }

    return 0;
}

程序输出为

The maximum value less than 3 is 2.2

Answer 3

感谢@Dietmar Kühl 的建议。我为作业制作了这个版本：

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

int main ()
{
   std::vector<double> vec{2.7,1,2.2,3.5,4,2.8,3.0};
   double elem = 3;
   auto it = std::max_element(vec.begin(),vec.end(),
   [elem](const double &x,const double &y)
   {
    if(y<elem & x<y) return true;
    else return false;
   });
   std::cout<<*it<<std::endl;
   return 0;
}

C++ - return 向量中小于给定输入的最大元素的最有效方法

C++ - Most efficient way to return largest element in vector less than given input

stl

vector