![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
No.4ベストアンサー
- 回答日時:
私もこの問題はソートと同じだと思いますが、
ソートのアルゴリズムは大抵O(n^2)かかるものであり、
O(n)で解けというのはかなり制約になります。
単純ソートを使ってしまうとO(n^2)になり、
ヒープソートやクイックソートだとO(n*log(n))になってしまいます。
O(n)でできるソートはあまり多くありません。
それでもたとえば「ビンソート」というのがあります。
・まず、配列をサーチして、最大値を選ぶ(nに比例)、
・配列B[1..maxA]を確保。
・もう一回配列Aをサーチして、B[A[x]]にフラグを立てる。(nに比例)
・配列Bを下からサーチして、k番目に小さい
(フラグが立っているk番目の)数を見つける。(最大でnに比例)
ただし、見てもらえばわかる通り、最大値が大きいと
必要なメモリがそのまま多くなってしまい、実用的ではありません。
O(n)のアルゴリズムは、参考URLの
『定本 Cプログラマのためのアルゴリズムとデータ構造』
近藤嘉雪著 ソフトバンクパブリッシング発行
に3種類記述されています。
参考URL:http://www.amazon.co.jp/exec/obidos/ASIN/4797304 …
ビンソートを使って解くことが出来ました.
おっしゃる通り最大値が大きいと実用的とは言え
ませんが,今回はメモリを意識する必要がないよう
なので,ビンソートが有効です.
ありがとうございました.
No.3
- 回答日時:
ヒープを積んで、積み終わり、根から1つづつ(ソート後の)データを順次取り出す時、k個目で止めれば良いのでは。
あるいはいっそのことソート後に、A(K)を取れば良いのではないですか。
この問題は実質ソートと同じことでしょう。ソートをしないでk番目が判るアルゴリズムがあるとは、私の力では予想できないです。
No.2
- 回答日時:
一つ考えてみました。
(1) まず、配列 A[1...n] とは別に、配列 F[1...n] を用意します。配列 F[1...n] の各要素を全て 0 で初期化します。
(2) A[1...n] の中から最小値 A[i] を求め、A[i] は使用済み、という意味で、F[i] に 1 をセットします。
(3) A[1...n] の中で、対応する F[1...n] が 0 のものの中から最小値を求め、(2) 同様に、最小値 A[j] に対して F[j] に 1 をセットします。
この手順を繰り返して、k 番目に小さい値を取得します。
説明のために
(1) → (2) → (3)
と書きましたが、実際には
(1) → (3) → (3) → ...
と (3) を k 回繰り返せば k 番目に小さい整数を取得できます。
C で書いてみました。
#include <stdio.h>
const CINT_N = 10;
int a[] = { 315, 130, 3, 27, 85, 9, 17, 83, 51, 38 };
void main()
{
int f[CINT_N];
int iMin; /* 最小値 */
int iInitMin; /* 暫定の最小値がセットされたとき 1 */
int iIndex; /* 最小値を指すインデックス */
int i, j, k;
/* f[1...n] を初期化 */
for( i = 0; i < CINT_N; i++ ) {
f[i] = 0;
}
/* 例として、3 番目に小さい整数を求める */
k = 3;
for( j = 1; j <= k; j++ ) {
iInitMin = 0;
for( i = 0; i < CINT_N; i++ ) {
if( f[i] == 0 ) {
if( iInitMin == 0 ) {
iMin = a[i]; /* 暫定の最小値をセット */
iIndex = i;
iInitMin = 1;
} else {
if( a[i] < iMin ) {
iMin = a[i];
iIndex = i;
}
}
}
}
/* j番目に小さい整数に対して使用済みのフラグをセットする */
f[iIndex] = 1;
}
printf( "%d 番目に小さい整数は %d です。\n", k, iMin );
}
ありがとうございます.これでk番目に小さい
整数を得ることができますね.
ただ今回の問題では "O(n)" で解くことが必要です.
このプログラムでは計算時間が O(n^2)になって
しまうように思います.
でも本当に丁寧に回答してくださり,ありがとうございました!
No.1
- 回答日時:
>ヒープを使ったりして…
というのはヒープソートのことでしょうか?
一旦、ソートして、ソートした結果を
配列 B[1...n] に格納してやれば B[k] が求める整数になると思うんですけど。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 計算機科学 アルゴリズムについて 1 2023/01/01 19:43
- Ruby 初心者プログラミング 3 2022/10/12 11:31
- 数学 【急募】共通テスト数II・Bの選択問題について質問です。 自分は確率分布は確実に取れるのでそこは確定 1 2022/12/26 17:05
- その他(プログラミング・Web制作) プログラミングって本来数学的な計算をする為のものではないのですか? 学校で配られたFortran90 11 2022/08/25 22:14
- Windows 10 この現象も、Microsoft Explorer のお粗末な仕様のためか? 2 2023/06/09 15:06
- Visual Basic(VBA) VBAで早押しゲームを作りたい 4 2022/05/12 13:46
- 数学 上三角行列のn乗の証明 2 2023/07/23 21:45
- 数学 【 数A 順列 】 問題 6個の数字0,1,2,3,4,5,を使ってできる次 のような整数は何個ある 7 2022/06/19 12:33
- 数学 数的推理の問題です。 この問題の解説に 「選択肢にルートが付く数字はありませんので、CD,ACのいず 2 2022/04/04 11:09
- その他(コンピューター・テクノロジー) アルゴリズム、配列のフローチャートの問題なのですが、全く分かりません… (ア)~(カ)に入るものを教 1 2023/06/29 21:19
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
リスト構造のソートで悩んでま...
-
C言語でリストのソートについて...
-
excel VBA の条件をつけての列...
-
C# DataGridView のヘッダーセ...
-
DataGridViewの複数列を連動し...
-
数字文字列のソート方法
-
線形リストのソートについて
-
ファイル名「1.jpg ~10.jpg~...
-
昇順ソート
-
整数の選択
-
VB.NETでファイル名順にファイ...
-
列のどこをクリックしてもソー...
-
構造体配列の並べ替え
-
2次元配列を複数項目でソートし...
-
C# DataTableの行をソートしてD...
-
mysqlで日本語の並び替え
-
n個の要素で出来る順列組み合...
-
excel VBA リストビューの行...
-
n番目に大きい数を求めるアル...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
System.IO.Directory.GetFiles...
-
VB.NETでファイル名順にファイ...
-
C言語・要素除去
-
C# DataGridView のヘッダーセ...
-
Excelですべての組合せ(重複組...
-
VBA基本構文の作り方 2列の...
-
なぜ?counterintuitive
-
ファイル名「1.jpg ~10.jpg~...
-
リスト構造のソートで悩んでま...
-
配列の問題
-
C# DataTableの行をソートしてD...
-
あるディレクトリ内のファイル...
-
excel VBA の条件をつけての列...
-
10個の整数を入力して小さい順...
-
文字列をソートする方法
-
excel VBA リストビューの行...
-
DataGridViewの複数列を連動し...
-
2次元配列を複数項目でソートし...
-
csvファイル内にてソートす...
-
n番目に大きい数を求めるアル...
おすすめ情報