4

我很难掌握应该如何使用std::nth_element，因为我有点生疏了。

裁判说：

重新排列 range[first,last)中的元素，使得第 n 个位置的元素是排序序列中该位置的元素。

我想获取向量子集的第 n 个元素，所以我想这样做：

std::nth_element (v.begin()+start-0, v.begin()+nTh-1, v.begin()+end);

将意味着v从start，直到end（不包括）向量 的子集，然后假设该子集已排序，定位nTh元素。

看来我的理解是错误的，因为这个玩具示例：

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

int main () {
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  std::random_shuffle (myvector.begin(), myvector.end());


  std::nth_element (myvector.begin() + 1 - 0, myvector.begin()+5-1, myvector.begin() + 5);
  std::cout <<  *(myvector.begin()+5-1) << std::endl;

  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

打印 9 作为请求的元素，而我期待 5。请问我错过了什么？

4

2 回答 2

1

尝试：

std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());

代替 ：

std::nth_element (myvector.begin() + 1, 
                  myvector.begin() + 4, 
                  myvector.begin() + 5);

您正在改组，然后nth_element只调用一个子序列。这样你就不能返回的元素应该是什么。如果你对整个序列都这样做，那么答案是5。

于 2018-05-05T17:04:29.547 回答
0

我想获取向量子集的第 n 个元素，所以我想这样做：

std::nth_element (v.begin()+start-0, v.begin()+nTh-1, v.begin()+end);

将意味着从开始到结束（不包括）获取向量 v 的子集，然后假设该子集已排序，定位第 n 个元素。

是的，这是真的。但这样做时，位置 v[0] 到 v[start-1] 和 v[end] 到 v[v.size() - 1] 中的任何元素都不会成为 nth_element 重新排列的一部分，它们将停留在他们是。您作为 nth_element() 的一部分的开始和结束已将这些元素排除在重新排列之外。

我想你想要

std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());

考虑整个向量（第 n 个元素的第一个和第三个参数）。

这意味着无论 random_shuffle 在哪里打乱了元素

std::random_shuffle (myvector.begin(), myvector.end());

因为 nth_element 正在考虑整个向量，所以 nth_element 的第二个参数，如果已排序，myvector 中的第 5 个项目应该是 5。注意，由于 nth_element 的工作方式，前面的项目将小于 5（并且以任何顺序）并且下一个项目将超过 5 个（并且以任何顺序）。

于 2018-07-05T01:31:28.970 回答