人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: momousi
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:アルゴリズム 抽出 整数 次元 配列
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● paffpaff
●20ポイント

http://www7.plala.or.jp/keny01/algorithm/

整列アルゴリズム

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

◎質問者からの返答

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


2 ● masi
●30ポイント

http://www.geocities.jp/yasuhiro_nasu/algorithm/bstree/

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

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

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


3 ● paraglider
●30ポイント

http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-alg...

いろいろなソートアルゴリズム

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ