3

在 astd::vector<unsigned int>中，我想找到小于某个数字的最大数字的元素的位置。例如：

v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

我想找到一个最大小于 8 的数字。那个数字是 7。

以下代码不正确，但这可能是我想要得到的。

std::vector<unsigned int>::iterator pnt = std::find_if (v.begin(), v.end(), [](const unsigned int& x) { return x < 8; && x == MAX; });
4

2 回答 2

6

如果你的向量总是排序的，那么你可以用对数复杂度来做

auto it = std::lower_bound(v.begin(), v.end(), 8); // first value >= 8
auto m = *((it != v.begin())? --it : it);

如果您的矢量未排序，但可以修改，您可以分两步完成：

auto it = std::partition(v.begin(), v.end(), [](int x) { x < 8 });
auto m = *(it != v.begin())? std::max_element(v.begin(), it) : it);

如果你不能修改你的矢量，你可以手工完成

auto max = 0;
for (elem: v) {
   if (elem < 8) 
       m = std::max(elem, m);
}
// m is now the max of all elements < 8

这两种最终方法都具有线性复杂性。后者可以通过使用Boost.Iterator库中的filter_iterator来概括，但是您已经深入到模板领域，所以只有在您反复需要这种魔法时才这样做。

于 2013-07-17T21:12:37.447 回答
0

我会创建一个函数来检查向量内是否有任何值，如果没有则抛出错误。然后我会保存低于遇到的最大值但高于当前找到的最大值的每个值。这就是我将如何实现它。

unsigned smaller_than ( const std::vector<unsigned int>& v, unsigned max) {

    bool intial_found = false;
    unsigned largest;
    unsigned i;
    for ( i = 0; i < v.size() ;++i){
        if ( v [i] < max ){
            largest = v[i];
            intial_found = true;
            break;
        }
    }
    if ( ! intial_found ) {
        throw "oops";/*of course you make a Nice std::exception for this case*/
    }
    for (  ; i < v.size(); i++ ) {
        if ( v[i] < max && v [i] > largest){
            largest = v[i];
        }
    }
    return largest;
}
于 2013-07-17T21:23:12.857 回答