2GメモリのPCで、重複なしの40億正整数からある整数を特定できますか？
問題の考え方：
40億のint（40億* 4）/ 1024/1024/1024約14.9G、明らかにメモリの2Gだけではありませんが、40億のデータをメモリに入れることは不可能です。この問題をすばやく解決する最善の解決策は、データをメモリに格納することです。したがって、問題は現在、2Gのメモリ空間に40億の整数を格納する方法です。Javaのint型の整数は32ビットの4バイトで、int型の整数を識別するためにビットを使用すると記憶領域が大幅に縮小され、40億/ 8/1024/1024は約476.83メガバイトなので、処理するためにこれらの40億の整数をメモリに入れることができます。
具体的なアイデア：
intは4バイト、即ち4×8 = 32ビットを占有し、我々は、Nが実行されるルックアップの合計数を表し、完全なデータを格納するために、[1 + N / 32]配列INT INT TMPの長さを適用する必要がありますtmpの各要素は、0から31までの10進数に対応する32ビットを占めることができるため、BitMapテーブルを使用できます。
tmp [0]：0〜31で表すことができます
tmp [1]：32〜63で表すことができます
tmp [2]は64〜95を表すことができます
.......
次に、10進数を対応するビットに変換する方法を次に見てみましょう。
40億のintデータが6,3,8,32,36、......と仮定すると、特定のBitMapは次のように述べています。
tmp配列内の添え字をどのように決定するかは、実際に整数を32で割ることによって行うことができます。たとえば、整数8を32で割って0に等し、8をtmp [0]にします。さらに、tmp [0]の32ビットのどれが8であるかを知るにはどうすればmod 32はmodでokです、再び8の整数、tmp [0]のmod 8の32は8の場合、整数8はtmp [0]の8ビット目（右から数えて）にあります。