0

1,000,000 個の浮動小数点値を含むファイルがあります。10,000 個の最大値を見つける必要があります。

私は考えていました：

  1. ファイルの読み取り
  2. 文字列を float に変換する
  3. float を max-heap (最大値がルートになるヒープ) に配置する
  4. すべての値がヒープに入ったら、ルートを 10,000 回削除し、それらの値を list/arraylist に追加します。

私は私が持っていることを知っています

  1. ヒープへの 1,000,000 回の挿入
  2. ヒープからの 10,000 回の削除
  3. リターン リストへの 10,000 件の挿入

これは良い解決策でしょうか？これは宿題用です。

4

4 に答える 4

7

あなたの解決策はほとんど良いです。これは基本的に、K個の要素を取得した後に停止するヒープソートO(NlogN)であり、実行時間を（フルソートの場合）からに改善しO(N + KlogN)ます。ここで、N=1000000およびK=10000です。

ただし、最初はヒープにN個の挿入を行うべきではありません。これには時間がかかるためO(NlogN)です。代わりに、線形時間で配列をヒープに変換するheapify操作を使用してください。

K個の数値を並べ替える必要がない場合は、選択アルゴリズムを使用して線形時間でK番目に大きい数値を見つけ、それより大きいすべての数値を出力できます。これはO(n)解決策を与えます。

于 2012-09-20T17:22:49.433 に答える
0

並べ替えは高価であり、入力セットは小さくありません。幸いなことに、あなたは順序を気にしません。必要なのは、上位Xの数字があることを知ることだけです。だから、ソートしないでください。

1,000,000から上位10,000を探す代わりに、100から上位1（つまり、単一の最大値）を探している場合、この問題をどのように処理しますか？これまでに見た中で最大の値を追跡し、それを次の数値および次の数値と比較して、より大きな値を見つけるか、入力がなくなるまで続ける必要があります。そのアイデアを、見ている入力サイズにまで拡張できますか？ビッグオーは何でしょうか（ヒント：各入力番号を1回だけ見ることになります）？

これは宿題だと言ったので最後に注意してください。クラスでヒープについて学習したばかりで、教師/教授がヒープソリューションを探していると思う場合は、そうです。あなたのアイデアは良いものです。

于 2012-09-20T18:09:24.963 に答える
0

1,000,000 個の整数を配列にソートし、最後の 10000 個を直接取得するために、mergesort (最悪の場合は n 回の操作をログに記録する) を使用するのはどうですか?

于 2012-09-20T17:21:50.710 に答える
-1

それらをすべて読み込んだ後、配列内の値をマージソートできますか? これは、値をソートするための高速な方法です。次に、your_array[10000] を要求すると、それが 10000 番目に大きいことがわかります。マージソートは、あなたが望むもののように聞こえます。また、本当に速度が必要な場合は、基数ソートの値をフォーマットすることを検討できます。これには少しフォーマットが必要ですが、それがこの問題を解決するための絶対的な最速の方法であるように思えます。

于 2012-09-20T17:20:30.010 に答える