Tencent には次のような学校募集の質問があります。
メモリが 2G しかない PC の場合、10G の整数を含むファイルから中央値を見つけて、アルゴリズムを作成します。
バケットソートや基数ソートなどいくつかの解決策がありますが、ヒープを使用して解決する方法を見つけました。元の単語は次のとおりです。
まず、 を見つけます。 1G の最大値を検索し、次にこの要素を使用して 2G の最大値を検索し、次に 2G の最大値を使用して 3G の最大値を検索します。もちろん、これには並べ替えは必要ありませんが、より多くのディスク操作が発生するため、詳細は分析される。下位ソートと外側ソートのどちらがディスク IO を多くしますか?
最大 1g の整数のヒープを作成します。要素が最大値未満の場合は、このようにして 1g 番目の整数を取得できます。最大の要素を取得し、この要素を使用して一度ヒープを再構築し、今回のヒープに入る条件を超える 1g 番目に大きい要素を追加します。これにより、ヒープを構築した後、2g 番目に大きい要素を取得できます。
最初、1G が何なのか理解できませんでした。10G のデータを 10 個に分割し、その 1G のデータを並べ替えて最大の意味を見つけることですか。
この解決策についていくつかアイデアをいただければ幸いです、ありがとうございます。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
ヒープは完全なバイナリ ツリーであるデータ構造です (そのため、その構造を保存するためにポインターは必要ありません)。各ノードは、大きな上部ヒープと小さな上部ヒープに対応し、その子ノードより大きくも小さくもありません。それぞれ。たとえば、小さな上部ヒープでは、ルート要素が最も小さくなります。したがって、
O(1)的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度，最坏情况下都是O(log(N))として使用できます。この一節は、(1G+1) データを収容できる小さな上部ヒープを最初に作成することで、その中で最小の要素をすぐに見つけられることを意味します。次に、10G のデータをすべて走査して挿入します。挿入後にヒープがいっぱいの場合 (ヒープ内に 1G+1 データがあります)。一番小さいものを削除してください。 。 。 。
最終結果は、ヒープ内のデータが最大の 1G データであり、ヒープの先頭が最小のデータになります。つまり、降順でソートした場合、このデータの位置が 1G の位置になります。たとえば、次のようになります。この数字は x です。
その後、上記のプロセスを再度続行しますが、違いは、x 未満の要素のみがヒープに挿入され、x 以上の要素は無視されることです。つまり、見つかった 1G データを無視した後、最大の 1G を見つけます。このように、最終ヒープの先頭は、ソート後の2G位置のデータとなります。 (ただし、重複データを扱う場合は注意してください)。 。 。 。などを繰り返して中央値を見つけます。
質問があるのですが、この種の質問はビットマップを使用して行うことはできませんか? 。 。
整数が0~2^32-1のような4byteの場合。次に、その値の範囲を保存するには、512M メモリのビットマップのみが必要です。 。 。 。 ?1. これらの 10G 数値を走査し、ビットマップに出現した数値をマークし、出現した異なる数値の数を数え、それを count として記録します。 2. ビットマップを走査し、カウント/2 番目のビットを見つけます。これがこの数値です。 。 。
この方法についてはまだいくつかの多岐にわたる質問がありますが、マスターが興味を持ったら、ぜひ見てください:
10 個のヒープに分割されているので、各ヒープの共通の境界値は何ですか?
10個の山に分けた場合、最悪の場合、クイックソートは何回の判断が必要になりますか？
計算量を減らすことはできますか？
@zonxin