5

私は次の関数を書きました

//O(n^2)
void MostCommonPair(char * cArr , char * ch1 , char * ch2 , int * amount)
{
    int count , max = 0;
    char cCurrent , cCurrent2;
    int i = 0 , j;
    while(*(cArr + i + 1) != '\0')
    {
        cCurrent = *(cArr + i);
        cCurrent2 = *(cArr + i + 1);
        for(j = i , count = 0 ; *(cArr + j + 1) != '\0' ; j++)
        {
            if(cCurrent ==  *(cArr + j) && cCurrent2 ==  *(cArr + j + 1))
            {
                count++;
            }
        }
        if(count > max)
        {
            *ch1 = cCurrent;
            *ch2 = cCurrent2;
            max = *amount = count;
        }
        i++;
    }
}

次の入力の場合

"xdshahaalohalobscxbsbsbs"

ch1 = b ch2=s量=4

しかし、私の意見では、関数は非常に非効率的です。文字列を1回だけ処理する方法、または実行サイズをO（n）に減らす方法はありますか？

4

4 に答える 4

5

char最大256個の値を保持できるため、[256 * 256]カウンターの2次元テーブルを設定し、文字列を1回実行して、文字列内の文字の各ペアに対応するカウンターをインクリメントできます。次に、256x256の数値のテーブルを調べ、最大のカウントを選択し、2D配列内の位置を確認することで、それがどのペアに属しているかを知ることができます。カウンタテーブルのサイズは文字列の長さに関係なく一定の値に固定されているO(1)ため、2つのネストされたループが必要な場合でも、その操作はです。

int count[256][256];
memset(count, 0, sizeof(count));
const char *str = "xdshahaalohalobscxbsbsbs";
for (const char *p = str ; *(p+1) ; p++) {
    count[(int)*p][(int)*(p+1)]++;
}
int bestA = 0, bestB = 0;
for (int i = 0 ; i != 256 ; i++) {
    for (int j = 0 ; j != 256 ; j++) {
        if (count[i][j] > count[bestA][bestB]) {
            bestA = i;
            bestB = j;
        }
    }
}
printf("'%c%c' : %d times\n", bestA, bestB, count[bestA][bestB]);

これがideoneのデモへのリンクです。

これは漸近的に可能な最速の解決策ですが（つまりO(N)、それより速くすることはできませんO(N)）、短い文字列ではパフォーマンスが良くないことに注意してください。実際、あなたのソリューションは、約256文字より短い、おそらくそれ以上の入力で、それを打ち負かします。このコードに適用できる最適化は多数ありますが、コードの主要なアイデアを最も純粋で単純な形式で明確に表示できるようにするために、それらを追加しないことにしました。

于 2012-12-20T20:18:11.360 に答える
4

O（n）ランタイムが必要な場合は、ハッシュテーブル（たとえば、JavaのHashMap）を使用できます。

  • 文字列を1回だけ繰り返します。一度に1文字ずつO（n）
  • 訪問したキャラクターごとに、あと1文字だけ先を見越してください（これはあなたのキャラクターペアです-それらを連結するだけです）O（1）
  • 見つかったそのような文字ペアごとに、最初にハッシュテーブルでそれを探します：O（1）
    • まだハッシュテーブルにない場合は、文字のペアをキーint 1として、値として追加します（これは、文字列で表示された回数をカウントします）。O（1）
    • すでにハッシュテーブルにある場合は、その値をインクリメントしますO（1）
  • 文字列の確認が完了したら、ハッシュテーブルでカウントが最も高いペアを確認します。O（m）（ここmで可能なペアリングの数;m <= n必然的に）
于 2012-12-20T20:23:27.243 に答える
1

はい、実行カウントを維持することにより、ほぼ直線的な時間でこれを行うことができます。

それは役に立ちますか？

于 2012-12-20T20:17:10.107 に答える
0

最も「共通のペア」とは、2つの連続した文字の最も一般的なセットを意味すると仮定します

擬似コードレベルで

 Read the first character into the "second character" register
 while(there is data)
    store the old second character as the new first character
    read the next character as the second one
    increment the count associated with this pair
 Select the most common pair

したがって、必要なのは、文字ペアに関連付けられた保存とカウント、および最も一般的なものを見つけるための効率的なアルゴリズムです。

于 2012-12-20T20:20:28.940 に答える