1

タスクは、ベクトルがソートされた場合、中央値 (n 番目の要素) がその位置にある重複のあるベクトルを部分的にソートすることです。小さい要素はすべて左側に配置し、大きい要素はすべて右側に配置する必要があります。中央値と同じ値を持つすべての要素は元の順序である必要がありますが、残りの要素ではありません。

これをどのように解決しますか？

私の最初の解決策：

  1. std::nth_element() を使用して中央値の要素を見つけます
  2. ベクトルをトラバースし、インデックスに関して中央値と同じ値を持つ要素のみを並べ替えます。これを効率的に行うにはどうすればよいですか？
4

1 に答える 1

0

partition または stable_partition を使用します (元の順序を維持するため)。

class Predicate{
    int median_value;
    public:
    Predicate(int med) : median_value(med) {}
    bool operator()(int x){
    return x < median_value;
    }
};

int main(){

vector<int> v{ 10, 20, 30, 10, 30};

int median = 20;

cout << "median  = " << median << endl;

stable_partition(v.begin(), v.end(), Predicate(median));

for ( auto i : v)
    cout << i << " ";
}
于 2015-05-22T08:08:25.497 に答える