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

単純ではない例をいくつか試してみたところ、3 番目の例では不連続な出力が得られました。

プログラム

#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 です。

いいえ、要素は常に連続しているわけではありません。

また、良いテストケースを考えずに、多くの重複要素を持つ長いランダム配列を生成し、それが成り立つかどうかを確認するだけの、さらに単純な方法だと思います。1回目か2回目で壊れると思います。

于 2015-05-21T09:20:00.917 に答える