1 
vector<int> data = {3, 1, 5, 3, 3, 8, 7, 3, 2}; 
std::nth_element(data.begin(), data.begin() + median, data.end());

这是否总是会导致：

data = {less, less, 3, 3, 3, 3, larger, larger, larger} ?

或者其他可能的结果是：

data = {3, less, less, 3, 3, 3, larger, larger, larger} ?

我已经在我的机器上尝试了多次，导致第 n 个值始终是连续的。但这不是证据；）。

它的用途：

我想构建一个独特的 Kdtree，但我的向量中有重复项。目前我正在使用 nth_element 来查找中值。问题是选择一个唯一/可重构的中位数，而不必再次遍历向量。如果中值是连续的，我可以选择一个唯一的中值，而无需太多遍历。

4

2 回答 2

1

我刚刚尝试了几个不那么简单的例子，第三个得到了不连续的输出。

程序

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

int main() {
   std::vector<int> a = {1, 3, 3, 2, 1, 3, 5, 5, 5, 5};
   std::nth_element(a.begin(), a.begin() + 5, a.end());
   for(auto v: a) std::cout << v << " ";
   std::cout << std::endl;
}

在 Linux 下使用 gcc 4.8.1，使用std=c++11, 给我输出

3 1 1 2 3 3 5 5 5 5

而第 n 个元素是 3。

所以不，元素并不总是连续的。

我还认为，即使是一种更简单的方法，也不需要考虑一个好的测试用例，只是生成具有许多重复元素的长随机数组并检查它是否成立。我认为它会在第一次或第二次尝试时中断。

于 2015-05-21T09:20:00.917 回答
1

不。文档没有具体说明这种行为，经过几分钟的实验，很容易找到一个测试用例，其中骗子在ideone上不连续：

#include <iostream>
#include <algorithm>

int main() {
    int a[] = {2, 1, 2, 3, 4};
    std::nth_element(a, a+2, a+5);
    std::cout << a[1];
    return 0;
}

输出：

1

如果受骗者是连续的，则该输出将是2.

于 2015-05-21T09:20:17.260 回答