6

次のような24.000要素の大きなベクトルがあります。

(1,1,1,1,3,3,3,3,3,3,5,5,5,...etc)

4-6-3..etcのように、同じ要素がいくつ並んでいるかを確認したい次のコードを使用します。

static int counter=1;
vector<int>numbers;

for(int n=0;n<numbers.size()-1;n++)
{
  if(numbers[n]==numbers[n+1])
  {
    counter++;
  }
  else if(numbers[n]!=numbers[n+1])
  {
   cout<<counter<<endl;
   counter=1;
  }
}

同じことをより速く行うアルゴリズムはありますか。

4

3 に答える 3

6

あなたのアルゴリズムはO(N)時間内にあり、比較のためにすべての一意の要素にアクセスする必要があるため、それは私にとって非常に最適なようです. 内部の状態を除去しelse()たり、一部のコンパイラ設定をオンにしたりして、あちこちでいくつかのサイクルを削減することはできますが、アルゴリズム的には良好な状態です。

入力がすでにソートされている場合は、一連のバイナリ検索を実行できます。これにより、O(N lg N)最悪の場合の複雑さが得られますが、等しい要素シーケンスの平均の長さによっては、平均的なケースはかなり低くなる可能性があります。

ところで、@AndyProwlが彼の答えで示しているように、標準ライブラリは、この種の低レベルのアルゴリズムでさえ行うのに本当に素晴らしいです。およびアルゴリズムadjacent_findにupper_boundは十分に文書化された複雑さがあり、イテレータ規則は、独自のコードに存在するエッジ ケースを保護します。この語彙を習得すれば、自分のルーチンで簡単に使用できます (また、Range が C++ に導入されれば、Range を作成するのも簡単になることを願っています)。

于 2013-05-08T10:39:23.910 に答える