7

vector の最大の要素である 5 つのインデックスを見つける方法は? たとえば、std::vector<int>元のベクトルを変更せずに 5 つの最大値のインデックスを見つける方法は?

4

5 に答える 5

13

std::partial_sort( v.begin(), v.begin()+5, v.end() )ある方法でベクトルを並べ替えます。5つの最小値が並べ替えられ、の先頭になりvます。残りは未分類のままです。

インデックスが必要で、元の値を保持するため：
新しいベクトルに0..n-1の数値を入力し、次v[a] > v[b]の代わりに実行する比較関数を指定しa > bます。

struct Comp{
    Comp( const vector<int>& v ) : _v(v) {}
    bool operator ()(int a, int b) { return _v[a] > _v[b]; }
    const vector<int>& _v;
}

vector<int> vx;
vx.resize(v.size());
for( int i= 0; i<v.size(); ++i ) vx[i]= i;
partial_sort( vx.begin(), vx.begin()+5, vx.end(), Comp(v) );

vx[0..4]インデックスが含まれています。

于 2012-09-18T11:41:20.917 に答える
1

元のベクターからコピーを作成し、STL の専用アルゴリズムで部分的に並べ替えることができますnth_element。

bool cmp (int i,int j) { return (i<j); }    
int main () {
      vector<int> myvector;
      vector<int>::iterator it;

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

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

      // using default comparison (operator <):
      std::vector<int> copy_of_orig = myvector;
      nth_element (copy_of_orig.begin(), copy_of_orig.begin()+5, copy_of_orig.end(), cmp);
      // Display the first five biggest elts.
      for (int i = 0; i < 5; ++i)
        std::cout << copy_of_orig[i] << std::endl;
}
于 2012-09-17T20:27:26.770 に答える
1

1 ソリューション:

解は O(n) です。ここで、n は検査対象のベクトルの要素数です。

NULL で初期化された、長さ 5 のベクトル反復子のデキューを作成する 検査中のベクトルの要素を読み取り、インデックスを push_back {アイデアは、読み取った新しい要素データがより小さいかどうかに応じて、新しいインデックスを前方または後方にプッシュすることですリア インデックスのデータ、またはフロント インデックスのデータより大きい場合、既にデキューにあるデータが NULL の場合は、push_front と push_back のどちらを使用しても問題ありません}。これにより、前から後ろにソートされた状態でデキューが維持されます。

読み取られる新しいデータが先頭のデータよりも大きい場合は、背面を削除し、現在のデータの反復子を前面にプッシュします。他に何もしない

繰り返しの最後に、デキューには上位 5 つの要素のイテレータが含まれます。

于 2012-09-17T20:29:36.480 に答える
1

もっとエレガントな方法があるかもしれませんが、今はそれを見つけるのに疲れています。次のようなことを行うことができます（テストされていないため、特にコーナーケースではそのままで動作するという保証はありませんが、動作するはずです）：

std::array<int, 5> indices = {-1,-1,-1,-1,-1};//-1 used as invalid index for cases where myVec.size()<5
for(int i = 0; i < myVec.size(); ++i)
{
    for(int j = 0; j < 5; ++j)
        if((indices[j] == - 1) || (myVec[i] > myVec[indices[j]]))
        {
            std::copy_backward(indices.begin() + j, indices.end() - 1, indices.end());
            indices[j] = i;
            break;
        }
}

5 つの最大の要素のリストを維持します。ベクトルの各要素について、最大の要素から開始し、新しい要素が大きいかどうかをテストし、そうであればインデックスを下にシフトして最初に挿入し、そうでない場合は 2 番目に大きい要素をテストします。を変更せず、かなり低いオーバーヘッドvectorで実行されます。O(n)

C++11 を使用できない場合は、 の代わりに常にstd::vector(またはint[5]本当に必要な場合) を使用できますstd::array。

于 2012-09-17T20:30:39.970 に答える
0

次のようなことをする必要があります。

  int largestNumbers [5]{0, 0, 0, 0, 0};

  for each( const int i in data ){
  {
    for (int index = 0; index < 5; index++){
       if (i > largestNumber[index]){
          largestNumber[index] = i;
       }
     }
  }
于 2012-09-17T20:34:32.623 に答える