26

ある 32 ビット符号なし整数 N に対して、長さが最大 ​​2 32の 32 ビット符号なし整数配列が与えられ、配列内のエントリの半分以上が N に等しいというプロパティがあります。各数値を見て N を見つけます。配列内で 1 回だけ使用し、最大 2 kB のメモリを使用します。

ソリューションは決定論的で、N を見つけることが保証されている必要があります。

4

8 に答える 8

61

ビットごとに 1 つの整数を保持し、配列内の整数ごとにこのコレクションを適切にインクリメントします。

最後に、一部のビットのカウントが配列の長さの半分よりも大きくなります。これらのビットによって N が決まります。もちろん、カウントは N が発生した回数よりも大きくなりますが、それは問題ではありません。重要なことは、N の一部ではないビットは半分以上発生することはなく(N には半分以上のエントリがあるため)、N の一部であるビットは半分以上発生する必要がある (発生するため) ということです。 N が発生するたびに、および任意の追加)。

(現時点ではコードはありません - ネットアクセスが失われようとしています。うまくいけば、上記は十分に明確です。)

于 2008-11-10T17:13:27.750 に答える
43

Boyer と Moore の "Linear Time Majority Vote Algorithm" - 答えに対する現在の推測を維持しながら配列を下ります。

于 2008-11-10T18:22:16.860 に答える
8

これは、2つの変数のみで実行できます。

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

最初の番号を疑わしい番号にして、リストをループし続けます。数が一致する場合は、疑惑の強さを1つ増やします。一致しない場合は、疑惑の強さを1つ下げます。疑惑の強さが0に達すると、現在の番号が容疑者の番号になります。これは、最も一般的な番号を見つけるためには機能せず、グループの50％を超える番号のみを検索します。suspicionStrengthリストの長さの半分より大きい場合は、チェックを追加したいという衝動に抵抗してください。これにより、常により多くの合計比較が行われます。

PS私はこのコードをテストしていません-あなた自身の危険でそれを使用してください。

于 2008-11-11T02:55:45.170 に答える
4

Jon のアルゴリズムの疑似コード (メモ帳 C++ :-)):

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);
于 2008-11-10T17:37:51.303 に答える
2

a0, a1, . . . , an−1シーケンスにリーダーが含まれている場合、異なる値の要素のペアを削除した後でも、残りのシーケンスには同じリーダーがあることに注意してください。実際、2 つの異なる要素を削除すると、そのうちの 1 つだけがリーダーになる可能性があります。n/2 − 1新しいシーケンスのリーダーは=(n−2)/2 回以上出現します。その結果、それはまだn − 2要素の新しいシーケンスのリーダーです。

O(n) 時間の複雑さを持つ Python 実装を次に示します。

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader
于 2015-05-29T17:58:11.780 に答える
2

これは、ストリーミング アルゴリズム (膨大な (潜在的に無限の) データ ストリームがある場合) の標準的な問題であり、このストリームを 1 回通過して、このストリームからいくつかの統計を計算する必要があります。

明らかに、ハッシュまたはソートを使用してアプローチできますが、潜在的に無限のストリームを使用すると、明らかにメモリが不足します。したがって、ここで何か賢いことをしなければなりません。

多数要素は、配列のサイズの半分以上に出現する要素です。これは、多数要素が他のすべての要素を合わせた数よりも多く発生することを意味します。または、多数要素が出現する回数を数えて、他のすべての要素の数を引くと、正の数が得られます。

したがって、ある要素の数を数え、他のすべての要素の数を差し引いて数字 0 を取得すると、元の要素は多数決要素になることはできません。これが正しいアルゴリズムの基礎である場合:

カウンターと可能な要素の 2 つの変数があります。カウンターが 0 の場合はストリームを反復します - 可能な要素を上書きしてカウンターを初期化します。数値が可能な要素と同じ場合はカウンターを増やし、そうでない場合は減らします。Python コード:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

O(n)アルゴリズムが前に非常に小さな定数(3 など)を使用していることは明らかO(n)です。O(1)また、初期化された変数が 3 つしかないため、空間の複雑さは のように見えます。n問題は、これらの変数の 1 つが(配列が同じ数値で構成されている場合)まで大きくなる可能性があるカウンターであることです。番号を保存するには、スペースnが必要です。理論的な観点からO(log (n))は、それは時間と空間です。実用的なものから、倍長整数に 2^128 の数値を収めることができ、配列内のこの要素数は想像を絶するほど膨大です。O(n)O(log(n))

また、アルゴリズムは過半数の要素がある場合にのみ機能することに注意してください。そのような要素が存在しない場合でも、何らかの数値が返されますが、これは間違いなく間違っています。(アルゴリズムを変更して多数決要素が存在するかどうかを判断するのは簡単です)

ヒストリー チャンネル: このアルゴリズムは、1982 年に Boyer, Moore によって発明され、Boyer-Moore 多数決アルゴリズムと呼ばれました。

于 2016-03-27T04:02:12.407 に答える
0

このアルゴリズムは、2K ルールに従っている場合とそうでない場合があります。関数呼び出しによるメモリ制限の違反を避けるために、スタックなどで書き直す必要があるかもしれませんが、そのような呼び出しの対数しかないため、これは必要ないかもしれません。とにかく、私は大学からの漠然とした記憶、または分割統治を含むこれに対する再帰的な解決策を持っています。秘密は、グループを半分に分割すると、半分の少なくとも 1 つが最大値に等しい半分以上の値をまだ持っていることです。 . 分割するときの基本的なルールは、上位の値の候補を 2 つ返すことです。そのうちの 1 つは上位の値で、もう 1 つは他の値 (2 位である場合とそうでない場合があります) です。アルゴリズム自体を忘れました。

于 2008-11-10T18:04:52.840 に答える
0

buti-oxa / Jason Hernandez の答えの正しさの証明。Jason の答えが buti-oxa の答えと同じであり、両方とも記述されたアルゴリズムが機能するはずの方法で機能すると仮定します。

調整された疑惑の強さは、最高値が選択されている場合は疑惑の強さと等しく、最高値が選択されていない場合は-疑惑の強さと等しいと定義されます。正しい数字を選択するたびに、現在の調整された疑いの強さは 1 ずつ増加します。間違った数字を選択するたびに、間違った数字が現在選択されているかどうかに応じて、1 減少するか 1 増加します。したがって、調整された疑惑の強さを終了する可能性のある最小値は、number-of[top values] - number-of[other values] に等しくなります。

于 2008-11-12T22:37:20.777 に答える