6

s長さの文字列がありnます。範囲内で最も頻繁に使用される文字を見つけるために使用する最も効率的なデータ構造/アルゴリズムは何i..jですか?

文字列は時間の経過とともに変化しません。 s[i], s[i + 1], ... ,の中で最も頻繁に使用される文字を要求するクエリを繰り返すだけですs[j]。

4

8 に答える 8

10

各文字の出現回数を保持する配列。文字列を 1 回繰り返しながら、それぞれの値を増やします。これを行っている間、配列内の現在の最大値を覚えておくことができます。または、配列の最後にある最大値を探します。

疑似コード

arr = [0]
for ( char in string )
   arr[char]++
mostFrequent = highest(arr)
于 2013-01-24T13:53:01.107 に答える
2

区間で効率的な結果を取得したい場合は、シーケンスの各インデックスで積分分布ベクトルを作成できます。次に、j + 1とiでの積分分布を減算することにより、s [i]、s [i + 1]、...、s[j]から間隔での分布を取得できます。

Pythonのいくつかの擬似コードは次のとおりです。私はあなたのキャラクターがcharsであると仮定します、それ故に256の配布エントリ。

def buildIntegralDistributions(s):
    IDs=[]        # integral distribution
    D=[0]*256
    IDs.append(D[:])
    for x in s:
        D[ord(x)]+=1
        IDs.append(D[:])
    return IDs

def getIntervalDistribution(IDs, i,j):
    D=[0]*256        
    for k in range(256):
        D[k]=IDs[j][k]-IDs[i][k]
    return D

s='abababbbb'
IDs=buildIntegralDistributions(s)
Dij=getIntervalDistribution(IDs, 2,4)

>>> s[2:4]
'ab'
>>> Dij[ord('a')]  # how many 'a'-s in s[2:4]?
1
>>> Dij[ord('b')]  # how many 'b'-s in s[2:4]?
1
于 2013-01-24T13:57:55.733 に答える
2

配列に対して 1 回反復を実行し、各位置について、その位置までに各文字が何回出現するかを覚えておいてください。だから、このようなもの：

"abcdabc"

インデックス 0 の場合:

count['a'] = 1
count['b'] = 0
etc...

インデックス 1 の場合:

....
count['a'] = 1
count['b'] = 1
count['c'] = 0
etc...

インデックス 2 の場合:

....
count['a'] = 1
count['b'] = 1
count['c'] = 1
....

等々。インデックス 6 の場合:

....
count['a'] = 2
count['b'] = 2
count['c'] = 2
count['d'] = 1
... all others are 0

この配列を計算した後、間隔 (i, j) 内の特定の文字の出現回数を一定時間で取得できます。計算するだけですcount[j] - count[i-1](ここでは ! に注意してi = 0ください)。

したがって、クエリごとに、間隔内のすべての文字ではなく、すべての文字を反復する必要があるため、10 ^ 6 文字を反復する代わりに、最大で 128 のみを渡します (ASCII シンボルのみがあると仮定します)。

欠点 - 使用しているアルファベットのサイズによっては、より多くのメモリが必要になります。

于 2013-01-24T14:01:16.010 に答える
1

空間と時間の複雑さの観点から、アルゴリズムの要件を指定する必要があります。

スペースの複雑さを主張する場合はO(1)、ソート（たとえば、使用可能な自然な比較演算子がない場合はビットの辞書式順序を使用）と、最も高い要素の出現回数をカウントするだけで、O(N log N)時間の複雑さが得られます。

時間の複雑さを主張する場合はO(N)、@ Luchian Grigoreのソリューションを使用してください。これにはO(N)、スペースの複雑さも含まれます（O(K)-文字のKアルファベットの場合）。

于 2013-01-24T16:00:43.547 に答える
0 
string="something"
arrCount[string.length()];

文字列にアクセスするたびに freq() を呼び出します

freq(char accessedChar){
arrCount[string.indexOf(x)]+=1
}

最も頻繁なchar呼び出しを取得するにはstring.charAt(arrCount.max())

于 2013-01-24T14:07:34.380 に答える
0

提案されているように、最も時間効率の良いアルゴリズムは、各文字の頻度を配列に格納することです。ただし、単純に文字で配列にインデックスを付けると、未定義の動作が発生する可能性があることに注意してください。つまり、UTF-8 でエンコードされたテキストなど、0x00 ～ 0x7F の範囲外のコード ポイントを含むテキストを処理している場合、せいぜいセグメンテーション違反が発生し、最悪の場合はスタック データが破損する可能性があります。

char frequncies [256] = {};
frequencies ['á'] = 9; // Oops. If our implementation represents char using a
                       // signed eight-bit integer, we just referenced memory
                       // outside of our array bounds!

これを適切に説明するソリューションは、次のようになります。

template <typename charT>
charT most_frequent (const basic_string <charT>& str)
{
    constexpr auto charT_max = numeric_limits <charT>::max ();
    constexpr auto charT_min = numeric_limits <charT>::lowest ();
    size_t frequencies [charT_max - charT_min + 1] = {};

    for (auto c : str)
        ++frequencies [c - charT_min];

    charT most_frequent;
    size_t count = 0;
    for (charT c = charT_min; c < charT_max; ++c)
        if (frequencies [c - charT_min] > count)
        {
            most_frequent = c;
            count = frequencies [c - charT_min];
        }

    // We have to check charT_max outside of the loop,
    // as otherwise it will probably never terminate
    if (frequencies [charT_max - charT_min] > count)
        return charT_max;

    return most_frequent;
}

同じ文字列を複数回繰り返し処理する場合は、上記のアルゴリズム ( as construct_array) を変更して、 を使用しstd::array <size_t, numeric_limits <charT>::max () - numeric_limits <charT>::lowest () + 1>ます。次に、最初の for ループの後、最大文字の代わりにその配列を返し、最も頻繁に使用される文字を見つけるアルゴリズムの部分を省略します。std::map <std::string, std::array <...>>最上位コードでa を構築し、返された配列をその中に格納します。次に、最も頻繁に使用される文字を見つけるためのコードをその最上位コードに移動し、キャッシュされたカウント配列を使用します。

char most_frequent (string s)
{
    static map <string, array <...>> cache;

    if (cache.count (s) == 0)
        map [s] = construct_array (s);
    // find the most frequent character, as above, replacing `frequencies`
    // with map [s], then return it
}

現在、これは文字列全体に対してのみ機能します。比較的小さな部分文字列を繰り返し処理する場合は、代わりに最初のバージョンを使用する必要があります。それ以外の場合、最善の策はおそらく 2 番目の解決策のようなことですが、文字列を扱いやすいチャンクに分割することです。そうすれば、イテレータが存在するチャンクの頻度を再計算するだけで、キャッシュからほとんどの情報を取得できます。

于 2013-01-24T17:32:51.603 に答える
0

文字列が定数であり、異なるものであり、クエリの発生に渡されると仮定しiますj。

処理時間を最小限に抑えたい場合は、

struct occurences{
    char c;
    std::list<int> positions;
};

std::list<occurences>各文字を保持します。高速検索のために、positions順序を維持できます。

メモリを最小限に抑えたい場合は、増分する整数を保持してループすることができますi..j

于 2013-01-24T14:08:51.953 に答える