8

私はコーディングコンテストで このpuzzle質問[ ]に直面しました。related to data structure

木の惑星があります (木のデータ構造ではなく、実際の木です!!)。そこには何十億、あるいは何兆もの木があります。王は、炭素年代測定法を使用して、すべての木の年齢の中央値 (年と整数) を見つけるように命じました。( Method does not matter.) 注: 中央値は、並べ替えられた数字のリストの「中間の数字」です。

制約:
1.最も古い木は 2000 歳であることが知られています。
2.-infinity から +infinity までの範囲の整数を格納できる単一のマシンがあります。
3.ただし、一度にメモリに格納できるそのような整数の数は 100 万です。

したがって、100 万個の整数を保存して次の整数を保存したら、既に保存されている整数を削除する必要があります。
そのため、樹木の年齢を数えながら、中央値を追跡する必要があります。
彼らはどのようにこれを行うことができますか?

私のアプローチ
外部ソートのバリアントを使用して、年齢をチャンクでソートし、ファイルに書き込みます。
[チャンクに] k-way マージを適用します。
上記のアプローチの問題は、ファイルを 2 回スキャンする必要があることです。

情報を使用する別のアプローチを考えることができます[ ]The oldest tree is known to be 2000 years old.
を取ることはできませんか?count arrayas range of ages of tree is fixed

知りたいのですが、より良いアプローチはありますか？
データをファイルに保存する必要がない方法はありますか?[ where only main memory is sufficient?]

4

2 に答える 2

9

これは、2001 年の整数のみを格納することで実行できます。考えられるさまざまな年齢の配列を作成する

ages[2001] // [0..2000]

木を数えるとき

ages[thisAge]++

次に、中央値の計算は簡単です。あなたが言及した2番目のアプローチでこのソリューションにヒットしたようですが、それから、もっと良いアプローチがあることを知りたいと言いますか?

データをファイルに保存する必要がない方法はありますか?[メインメモリだけで十分な場合]

メインメモリが十分な方法が存在するかどうかを尋ねる理由がわかりません。2001 年の整数の配列はメイン メモリに収まりませんか?

上記のアプローチを使用すると、カウントの配列を埋めてから、カウントを反復して中央値を計算し、合計を維持することができます。合計が木の総数の半分に達すると、中央値になります。これには、カウントするためにすべてのツリーを 1 回通過する必要があり、加えて数 <=2001 のカウント配列の一部を通過する必要があります。これは O(n) です。代わりに、この配列を使用して中央値を追跡することもできますが、解を実際に改善することはできません。

于 2012-06-24T13:23:54.360 に答える
2

あなたが推奨したアプローチ (2001 年の配列) は O(n) であり、ツリーごとに 1 つの高速操作が行われるため、これが最適です。

まあ、ほぼ最適です。カウント中のある時点で、結果を変更するには残りのツリーの数が不十分になります。たとえば、半分 + 1 本の木を数え、すべてが正確に 100 年である場合、私の答えは 100 年になります。

しかし、木の年齢が十分に分散している場合、必要な木の数は総数に近くなります。

于 2012-06-24T13:37:00.740 に答える