查找向量中阈值以上的连续值的最佳方法

Smash 发表于 Dev

粉碎

找到阈值以上的最小连续值的最快方法是什么？

假设我有一个值向量：

std::vector<int> v = [10 25 8 49 50 61 55 45 34 10 8]

一种简单的方法是遍历向量。

int threshold = 40;
int consecutive = 5;

bool success = false;

for(int i = 0; i < v.size()-consecutive; ++i)
{
    int counter = 0;

    while(i+counter < v.size())
    {
        if(v[i+counter] > threshold)
        {
            counter++;
        }
    }

    if(counter >= consecutive)
    {
        success = true;
        break;
    }
}

编辑：对于@cmbasnett

success = true如果在向量中找到5连续值，40则预期结果为v，false否则为。

马特纽波特

您可以使用以下方法执行此操作std::search_n()：

bool success = search_n(begin(v), end(v), 5, 40, [](int x, int y) { return y < x; }) != end(v);

现场版。

通过跳过失败的元素，您可以更有效地编写自己的优化版本，有点像Boyer-Moore-Hoorspool搜索：

template<typename It, typename T>
bool contains_n_gt_x(It first, It last, size_t n, const T& x) {
    for (auto curr = first; first != last;) {
        first = find_if(curr, last, [&](const auto& y){ return x < y; });
        curr = find_if(first, last, [&](const auto& y){ return !(x < y); });
        if (distance(first, curr) >= n) return true;
    }
    return false;
}

现场版。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。