使用 stdnth 元素查找中位数(或其他分位数)
所述 std::nth_element
算法需要三个迭代器:一个迭代开始时, N 个位置,并结束。一旦函数返回,第 n 个元素(按顺序)将是第 n 个最小元素。 (该函数具有更复杂的重载,例如,一些采用比较函子;请参阅上面的链接了解所有变体。)
注意此功能非常有效 - 它具有线性复杂性。
为了这个例子,让我们将长度为 n 的序列的中位数定义为位置为⌈n/2⌉的元素。例如,长度为 5 的序列的中值是第 3 个最小元素,长度为 6 的序列的中值也是如此。
要使用此函数查找中位数,我们可以使用以下内容。假设我们开始
std::vector<int> v{5, 1, 2, 3, 4};
std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();
std::vector<int>::iterator med = b;
std::advance(med, v.size() / 2);
// This makes the 2nd position hold the median.
std::nth_element(b, med, e);
// The median is now at v[2].
为了找到第 p 个分位数 ,我们将改变上面的一些行:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
并在 pos
处寻找分位数。