このようなアルゴリズムについて解説しているところはないでしょうか?k<<nの条件で、n個の整数を要素とする1次元配列のXの中から、要素の値の小さい順にk個までの要素を抽出するためのアルゴリズム。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2003/11/09 00:04:44
  • 終了:--

回答(3件)

id:paffpaff No.1

paffpaff回答回数430ベストアンサー獲得回数122003/11/09 00:13:57

ポイント20pt

整列アルゴリズム

整列して(昇順)小さいほうからk個とりだせばよいのでは?

id:momousi

nがすごく大きい数という条件なので、できれば整列させずにk個のデータが得られるほうがいいのですが。。

2003/11/09 00:40:06
id:masi No.2

masi回答回数356ベストアンサー獲得回数02003/11/09 01:33:19

ポイント30pt

k個の整数を要素とする二分探索木を作成。

X(0)~X(n)までの要素を順に二分探索木に追加していき、要素の数がk個より多くなったら最大のものを削除。

追加は、追加する場所を探す log(k-1) 回の比較の後、ノードを追加ってのが手間そうですが,,,

id:paraglider No.3

paraglider回答回数1ベストアンサー獲得回数02003/11/09 09:47:33

ポイント30pt

k個の配列Yを用意し、初期値として十分に大きい値を設定しておきます。

X(1)<Y(k)なら、X(1)とY(k)を入れ替えて、

Yをソートします。このソートは表記のサイトに色々説明されています。

これをX(n)まで繰り返すだけです。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません