配列内で最も一般的なエントリを見つける
https://stackoverflow.com/questions/278488
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
最大 2 の長さの 32 ビット符号なし整数配列が与えられます。32, 、32 ビット符号なし整数 N については、配列内のエントリの半分以上が N に等しいという特性を持ちます。配列内の各数値を 1 回だけ調べて、最大 2 KB のメモリを使用して N を求めます。
解は決定論的であり、N が見つかることが保証されている必要があります。
解決
ビットごとに整数を1つ保持し、配列内の整数ごとにこのコレクションを適切に増分します。
最後に、一部のビットのカウントは配列の長さの半分より大きくなります-これらのビットはNを決定します。もちろん、カウントはNが発生した回数よりも高くなりますが、そうではありません問題。重要なことは、Nの一部ではないビットは半分以上（
（現時点ではコードはありません-ネットアクセスが失われようとしています。上記が十分に明確であることが望まれます。）
他のヒント
ボイヤーとムーアの＆quot;線形多数決投票アルゴリズム＆quot ; -答えを現在の推測で維持しながら配列を下っていきます。
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私はこのコードをテストしていません-あなた自身の危険でそれを使用してください。
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);
シーケンスが 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
これは、ストリーミングアルゴリズムの標準的な問題です（データの巨大な（潜在的に無限の）ストリームがある）、このストリームから統計を計算し、このストリームを1回通過する必要があります。
明らかに、ハッシュまたはソートでアプローチできますが、潜在的に無限ストリームでは、明らかにメモリ不足になります。したがって、ここで何かスマートなことをする必要があります。
多数の要素は、配列のサイズの半分以上で発生する要素です。これは、多数要素が他のすべての要素よりも多く発生することを意味します。または、回数をカウントすると、多数要素が表示され、他のすべての要素の数を引くと、正の数が得られます。
つまり、ある要素の数を数えて、他のすべての要素の数を引いて0を取得すると、元の要素は多数決要素になりません。これは正しいアルゴリズムの基礎である場合：
2つの変数、counterおよび可能な要素があります。カウンターが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）であり、 O（n）（3など）の前に非常に小さな定数があることは明らかです。また、3つの変数のみが初期化されているため、スペースの複雑さは O（1）のように見えます。問題は、これらの変数の1つが n に達する可能性のあるカウンターであるということです（配列が同じ数で構成されている場合）。そして、数値 n を保存するには、 O（log（n））スペースが必要です。したがって、理論的な観点からは、 O（n）時間と O（log（n））スペースです。 実用的から、2 ^ 128の数値を倍長整数に収めることができ、配列内のこの要素の数は想像を絶するほど膨大です。
また、アルゴリズムは多数要素がある場合にのみ機能することに注意してください。そのような要素が存在しない場合でも、いくつかの番号が返されますが、間違いがあります。 （アルゴリズムを変更して、多数要素が存在するかどうかを確認するのは簡単です）
履歴チャネル：このアルゴリズムは、1982年にボイヤー、ムーアによって発明され、 Boyer＆＃8211;ムーア多数決アルゴリズム。
このアルゴリズムの思い出がありますが、2Kルールに従う場合と従わない場合があります。関数呼び出しによるメモリ制限の解消を回避するために、スタックなどで書き換える必要があるかもしれませんが、そのような呼び出しの対数の数しかないため、これは不要な場合があります。とにかく、大学からのあいまいな思い出や、分割と征服を伴うこれに対する再帰的な解決策があります。秘密は、グループを半分に分割すると、半分の少なくとも1つが最大値に等しい値の半分以上をまだ持っているということです。分割する際の基本的なルールは、2つの候補最高値を返すことです。そのうちの1つは最高値で、もう1つは他の値（2位である場合も2位でない場合もあります）です。アルゴリズム自体を忘れています。
buti-oxa / Jason Hernandezの答えの正しさの証明。Jasonの答えがbuti-oxaの答えと同じであり、両方とも説明されているアルゴリズムが機能するはずであると仮定します。
調整された疑いの強さは、上限値が選択されている場合は疑いの強さ、上限値が選択されていない場合は-疑いの強さと等しいと定義します。正しい数字を選ぶたびに、現在の調整された疑いの強さは1増加します。間違った数字を選ぶたびに、間違った数字が現在選択されているかどうかに応じて1ずつ下がるか、1ずつ増えます。したがって、可能な限り調整された最小の疑いの強さは、number-of [top values]-number-of [other values]
に等しくなります