たとえば、配列の答えは次のとおりです。
1、11、3、95、23、8、1
1 は 2 回発生するのに対し、他のすべての要素は 1 回しか発生しないため、1 になります。
私がstackoverflowで見たこの質問に似た多くの質問は、絶対多数を見つけることを求めます（答えは長さnの配列で少なくともn / 2発生します）、またはソートまたはハッシュテーブルを使用して質問に答えます。前者は私が求めているものではなく、後者は遅すぎるか（ソートには O(n log n) ）、メモリを使いすぎます（ハッシュテーブルには O(n) ）。
そのようなアルゴリズムは存在しますか？そうでない場合、それが不可能である理由を示す証拠はありますか? ソースを含めるといいでしょう。
ここからのアイデアを使用してください：
O(n) 時間と O(1) 空間の複雑さで配列内の繰り返し数を見つけるにはどうすればよいですか
そして、 sort のカウントに似た手法を適用します。つまり、N 個のビン (サイズ N の配列) を作成します。ここで、N は予想される最大の整数です。これはまだ O(1) スペースです。次に、元の配列を O(n) 時間で反復し、値iに遭遇したら、結果配列のインデックスiを 1 増やします。次に、結果配列を反復し (再び O(1) 時間)、最大の単一値。その値のインデックスは、元のリストで最も一般的な値になります。
最も一般的な要素を見つけるためにスペースを固定したい場合は、要素の最大ビット数が必要です。そうしないと、大きな入力配列に大きな入力数値が含まれ、数値を表すビットが結果を格納するための固定スペースよりも大きくなる可能性があります。
サポートkする最大数の長さを とします。各数値の出現回数をカウントするバケットの配列を単純に作成しようとすると2^k(カウンター ソート)、同じ数値で構成される配列を受け取る可能性があります。この場合、アルゴリズムはlog(n)合計を格納するためのスペースを必要とすることになります。[*]
1問題のより単純なバージョンを見ると、入力に's または'sがさらにあるかどうかを判断0します。これを行うにはスタックが必要だと思います (どれだけを保存するか、先行している1か0)、したがって一定です。入力の長さをk = 1ビットサイズに制限したとしても、スペースは不可能です。
あなたの問題はより一般的であり（k > 1、まだ修正されています）、一定でないスペースも必要になるため、質問が言葉で表現されているため、それは不可能です。
[*] カウンターがスペースの複雑さを持っていると想定する場合はO(1)、カウンター ソート アプローチを使用できますが、そうすることで、入力配列の最大サイズに上限を設けることになります (許容される場合と許容されない場合があります)。に関してはk、配列の入力要素の最大ビット数、およびcカウンターの最大ビット数に関しては、配列が最大2^k * 2^c要素を持つことができます (カウンターの 1 つが次の要素でオーバーフローします)。これに対処するには、タイム ステップを追加してカウンタをデクリメントし、すべてのカウンタが非 である場合に各要素が処理された後にO(1)常に最小値になるようにして、絶対値ではなく相対値にすることができます。これには00O(1)すべてがゼロ以外の場合、各要素で実行する場合にのみO(2^k) = O(1)カウンターをデクリメントする必要があるためです。1アルゴリズムは任意の大きな入力を処理できるようになりましたが、2 つの値を持つサブ配列を持ちa、カウンター戦略bを使用するような入力配列はcount(a) - count(b) > 2^c = max(counter)、一部の入力に対して失敗します。実際、空間複雑度カウンター アプローチに依存した結果、同一の要素O(1)で始まるすべての配列は2^c + 1、このアルゴリズムでは処理できなくなります。
これは完全な答えではありませんが、この問題が難しい理由を明らかにするのに役立つはずです。
最も一般的な要素を見つけるために配列を (ある順序で) 1 回スイープするアルゴリズムを設計したいとします。アルゴリズムの実行中、一部のデータ構造を保持することが許可されていますS。Sにどのくらいの情報が必要か、そしてそれをO(1)メモリに格納できるかどうかを見てみましょう。
アルゴリズムがk配列の最初の要素を処理したとします。Sこれで、範囲内で最も一般的な要素がわかりますa[0..k]。ただし、k+1最初の要素がわかっているとしたら、その範囲で最も一般的な要素もわかっていることになりますa[0..k+1]。それができない場合、 が の場合、アルゴリズムは機能しませnんk+1。より一般的には、要素a[k..m]との知識があれSば、 で最も一般的な要素がわかりa[0..m]ます。
上記の引数を使用して、 から情報を抽出できますS。範囲内の整数で作業しているとします[0,u](元の配列がスペースを取る場合、何らかの範囲が必要ですO(n))。元の最も一般的な要素が5である場合、最も一般的な要素が変更されるまで を追加0します。cゼロを取った場合は、 よりも多くのa[0..k]が含まれている必要があります。この引数を繰り返すと、各要素がに何回存在したかを正確に知るために解くことができる多くの線形方程式が得られます。c50[0,u]a[0..k]
これは、スイープを行うすべてのデータ構造が、見られたすべての要素のカウントを (圧縮された方法で) 保存する可能性があることを示しています。数学に興味がある場合は、見分けがつかないアイテムを区別可能なビンに分割する方法の数のログである、見た後に保存されたn数値です。以上です。log(n+u-1 choose n)nulog(u^n/n!) >= nlogu-nlogn
結論: 配列のパスを 1 回だけ実行するアルゴリズムは、これまでに見たすべてのカウントを格納するのに必要なだけのメモリを使用する必要があります。nこれに比べて小さい場合は、記憶の単語uを格納することに相当します。n
(追加のメモリの代わりに、既存の配列を上書きすることもできます)。
ここで探索することは他にもたくさんあります。たとえば、複数のパスが上記の引数にどのように影響するか。ただし、この時点で停止する必要があると思います:)、しかし、大きな を持つ線形時間アルゴリズムが余分なメモリuで逃げることができるとは思えません。O(1)