19

並べ替えられていない長さ n の配列/ベクトルの k 個の最大要素のインデックスを、C++ で k < n で見つける必要があります。nth_element() を使用して k 番目の統計を見つける方法を見てきましたが、nth_statistic に対して k 回の呼び出しを行う必要があるように思われるため、これを使用することが私の問題にとって正しい選択であるかどうかはわかりません。複雑さは O(kn) になりますが、これは可能な限り優れているのでしょうか? または、O(n) だけでこれを行う方法はありますか?

nth_element() なしで実装すると、配列全体を 1 回反復処理して、各ステップで最大の要素のインデックスのリストを作成する必要があるようです。

標準 C++ ライブラリに、これをワンライナーにするもの、またはこれを自分でわずか数行で実装するための巧妙な方法があるものはありますか? 私の特定のケースでは、k = 3、n = 6 であるため、効率は大きな問題ではありませんが、任意の k と n に対してこれを行うクリーンで効率的な方法を見つけるとよいでしょう。

並べ替えられていない配列の上位 N 要素をマークするのは、おそらく SO で見つけることができる最も近い投稿で、Python と PHP に投稿されているようです。

4

7 に答える 7

9

これが私が望むことを行う私の実装であり、かなり効率的だと思います：

#include <queue>
#include <vector>
// maxindices.cc
// compile with:
// g++ -std=c++11 maxindices.cc -o maxindices
int main()
{
  std::vector<double> test = {0.2, 1.0, 0.01, 3.0, 0.002, -1.0, -20};
  std::priority_queue<std::pair<double, int>> q;
  for (int i = 0; i < test.size(); ++i) {
    q.push(std::pair<double, int>(test[i], i));
  }
  int k = 3; // number of indices we need
  for (int i = 0; i < k; ++i) {
    int ki = q.top().second;
    std::cout << "index[" << i << "] = " << ki << std::endl;
    q.pop();
  }
}

出力が得られます：

index[0] = 3
index[1] = 1
index[2] = 0
于 2013-02-15T22:29:33.273 に答える
9

これは、O(nlogk)代わりに実行される @hazelnusse の改良版である必要があります。O(nlogn)

#include <queue>
#include <iostream>
#include <vector>
// maxindices.cc
// compile with:
// g++ -std=c++11 maxindices.cc -o maxindices
int main()
{
  std::vector<double> test = {2, 8, 7, 5, 9, 3, 6, 1, 10, 4};
  std::priority_queue< std::pair<double, int>, std::vector< std::pair<double, int> >, std::greater <std::pair<double, int> > > q;
    int k = 5; // number of indices we need
  for (int i = 0; i < test.size(); ++i) {
    if(q.size()<k)
        q.push(std::pair<double, int>(test[i], i));
    else if(q.top().first < test[i]){
        q.pop();
        q.push(std::pair<double, int>(test[i], i));
    }
  }
  k = q.size();
  std::vector<int> res(k);
  for (int i = 0; i < k; ++i) {
    res[k - i - 1] = q.top().second;
    q.pop();
  }
  for (int i = 0; i < k; ++i) {
    std::cout<< res[i] <<std::endl;
  }
}

8 4 1 2 6

于 2016-07-15T08:38:53.840 に答える
7

質問には部分的な答えがあります。つまり、n 番目の統計の前にある要素が it より大きくなく、それに続く要素が it より小さいstd::nth_elementというプロパティを持つ「n 番目の統計」を返します。

したがって、k 個の最大要素を取得するには、 を 1 回呼び出すだけで十分です。std::nth_element最小 (またはこの場合は k-最小) の要素を見つけるために各要素に少なくとも 1 回アクセスする必要があるため、時間の複雑さは理論的には最小の O(n) になります。これらの k 個の要素を並べ替える必要がある場合は、O(k log(k)) になるように並べ替える必要があります。したがって、合計で O(n + k log(k)) になります。

于 2014-05-06T04:33:50.317 に答える
3

クイックソートアルゴリズムの基礎を使用して、必要なことを実行できます。ただし、パーティションを並べ替える代わりに、目的の範囲から外れているエントリを取り除くことができます。

これは「クイックセレクト」と呼ばれ、C++の実装は次のとおりです。

int partition(int* input, int p, int r)
{
    int pivot = input[r];

    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;

        while ( input[r] > pivot )
            r--;

        if ( input[p] == input[r] )
            p++;
        else if ( p < r ) {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

int quick_select(int* input, int p, int r, int k)
{
    if ( p == r ) return input[p];
    int j = partition(input, p, r);
    int length = j - p + 1;
    if ( length == k ) return input[j];
    else if ( k < length ) return quick_select(input, p, j - 1, k);
    else  return quick_select(input, j + 1, r, k - length);
}

int main()
{
    int A1[] = { 100, 400, 300, 500, 200 };
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl;
    int A2[] = { 100, 400, 300, 500, 200 };
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl;
    int A3[] = { 100, 400, 300, 500, 200 };
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl;
    int A4[] = { 100, 400, 300, 500, 200 };
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl;
    int A5[] = { 100, 400, 300, 500, 200 };
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl;
}

出力：

1st order element 100
2nd order element 200
3rd order element 300
4th order element 400
5th order element 500

編集

その特定の実装の平均実行時間はO（n）です。ピボットの選択方法により、クイックソートの最悪の場合の実行時間を共有します。ピボットの選択を最適化することにより、最悪の場合もO（n）になります。

于 2013-02-15T20:39:46.023 に答える
2

標準ライブラリはインデックスのリストを取得しません (冗長なデータの受け渡しを避けるように設計されています)。ただし、n 個の最大要素に関心がある場合は、何らかのパーティショニングを使用します ( と は両方ともstd::partitionO std::nth_element(n) です)。

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

struct Pred {
    Pred(int nth) : nth(nth) {};
    bool operator()(int k) { return k >= nth; }
    int nth;
};

int main() {

    int n = 4;
    std::vector<int> v = {5, 12, 27, 9, 4, 7, 2, 1, 8, 13, 1};

    // Moves the nth element to the nth from the end position.
    std::nth_element(v.begin(), v.end() - n, v.end());

    // Reorders the range, so that the first n elements would be >= nth.
    std::partition(v.begin(), v.end(), Pred(*(v.end() - n)));

    for (auto it = v.begin(); it != v.end(); ++it)
        std::cout << *it << " ";
    std::cout << "\n";

    return 0;
}
于 2013-02-15T22:06:22.217 に答える
0

O(n)これは、1 回の注文統計計算で間に合うように行うことができます。

  • 次rのk統計量を
  • 2 つの空リストbiggerと を初期化しますequal。
  • 各インデックスについてi:
    • の場合、array[i] > r追加ibigger
    • の場合、array[i] = r追加iequal
  • 2つequalのリストの長さの合計がk
  • 2 つのリストの連結を返します。

当然のことながら、すべての項目が異なる場合、必要なリストは 1 つだけです。また、必要に応じて、2 つのリストを 1 つに結合するトリックを行うこともできますが、コードはより複雑になります。

于 2016-07-15T08:49:06.747 に答える
0

次のコードは、必要な複雑さの制約を満たさない可能性がありますが、前述の優先キューの興味深い代替手段になる可能性があります。

#include <queue>
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

std::vector<int> largestIndices(const std::vector<double>& values, int k) {
    std::vector<int> ret;

    std::vector<std::pair<double, int>> q;
    int index = -1;
    std::transform(values.begin(), values.end(), std::back_inserter(q), [&](double val) {return std::make_pair(val, ++index); });
    auto functor = [](const std::pair<double, int>& a, const std::pair<double, int>& b) { return b.first > a.first; };
    std::make_heap(q.begin(), q.end(), functor);
    for (auto i = 0; i < k && i<values.size(); i++) {
        std::pop_heap(q.begin(), q.end(), functor);
        ret.push_back(q.back().second);
        q.pop_back();
    }

    return ret;
}

int main()
{
    std::vector<double> values = { 7,6,3,4,5,2,1,0 };
    auto ret=largestIndices(values, 4);
    std::copy(ret.begin(), ret.end(), std::ostream_iterator<int>(std::cout, "\n"));
}
于 2016-08-26T10:55:00.023 に答える