不要调整算法。算法很明确(“找到最小值”)。改为调整搜索条件,并保持在 O(n) 范围内。
代码。
#include <algorithm>
#include <vector>
#include <iostream>
int main () {
// std::min_element()
std::vector<float> vec;
vec.push_back(0);
vec.push_back(-1);
vec.push_back(-2);
vec.push_back(2);
vec.push_back(4);
auto cmp = [](float lhs, float rhs) {
const bool lz = lhs < 0,
rz = rhs < 0;
if (lz && rz) return lhs < rhs;
if (lz) return false;
if (rz) return true;
return lhs < rhs;
};
const float mp = *std::min_element (vec.begin(), vec.end(), cmp);
std::cout << mp << '\n';
// demonstration of our comparison
sort (vec.begin(), vec.end(), cmp);
for (auto it=vec.begin(), end=vec.end(); it!=end; ++it)
std::cout << *it << " ";
std::cout << std::endl;
}
输出。
0
0 2 4 -1 -2
解释。
我们的排序函数被编码在cmp
. 它检查其操作数的符号。如果两者都是负数,则较大的获胜。如果只有 LHS 是负数,则在排序中自动首选 RHS。相反,如果 RHS 为负,则首选 LHS。两者都是积极的,我们回到正常秩序。
好消息是,这在范围内和 O(n) 中只运行了一次。