２番目の最大値を求める

質問

n個の要素をもった配列で、２番目に大きい要素を見つけるコードを書きたいのですが、合っているのか不安になって、質問させてもらいます。

アルゴリズムとしては、まず、n-1回の比較をしてその中でmaxを見つけ、残りのn-1個の要素のなかでn-2回の比較をしてそのn-1個の配列のmaxを見つければ、２番目に大きい要素を見つけられると考えました。

int main(void) {
int E[n];
int i, j, temp;

for(i=0;i<N;i++){
for(j=1;j<N-i;j++){
if(E[j-1]>E[j]){
temp=E[j-1];
E[j-1]=E[j];
E[j]=temp;
}
}
}
return E[j];
}

これであっていますでしょうか？

よろしくお願いいたします。

回答No.7

akayoroshi

簡単な１重ループだけでで可能です
int max, second, i;
max=0;
for ( int i=1; i<n; ++i ) if ( E(max)<E(i) ) max=i;
int second=0;
if ( max==0 ) second=1;
for ( i=second+1; i<max; ++i ) if ( E(second)<E(i) ) second=i;
for ( i=max+i; i<n; ++i ) if ( E(second)<E(i) ) second=i;

回答No.6

midly

最大値を調べるのはそれでいいと思いますが
２番目の値を調べるときに、最大値を選んでしまう可能性があります。
下記は一重ループの例です。
該当データが複数ある場合には最初のデータを有効としています。複数全てチェックする場合には結果格納変数を配列にする等の処理が必要です
flagはnumに有効なデータが入っているか否かを示すフラグで、初期値を工夫するとflag処理は要らなくなり、ループの中はifが二つになります。
実際データ量が多いときには、最初に出会う値の違う２値を初期値にしてループ中のifを２つにした方が早そうです。

#define MAX (16)
void main(void)
{
int c[MAX]={1,2,3,3,4,4,5,6,7,8,8,8,9,9,9,-1};
int i, num1, num2, i1, i2, flag1, flag2;
flag1 = flag2 = 0;
i1 = i2 = -1;
for (i = 0; i < MAX; i++){
if (0 == flag1){
num1 = c[i];i1 = i;flag1 = 1; //最大値初期値
}
else if (num1 < c[i]){ //最大値交代
num2 = num1;i2 = i1;flag2 = 1; //それまでの最大値が２番目に
num1 = c[i];i1 = i; //新最大値
}
else if (num1 > c[i]){
if (0 == flag2){
num2 = c[i];i2 = i;flag2 = 1;//２番目初期値
}
else if (num2 < c[i]){ //２番目交代
num2 = c[i];i2 = i;
}
}
}
if (0 <= i2){
printf("second c[%d]=%d\n",i2,num2);
}
else{
printf("second is nothing\n");
}
printf("(ref)max c[%d]=%d\n",i1,num1);
}

回答No.5

goosyu

＞これであっていますでしょうか？
　アルゴリズムとして最善かということは別にして，昇順ソートして結果E[n-2]を参照すれば，答えが求められますので正しいと思います。（main()の戻り値が答えなら間違えです。）
　但しE[]に同じ値が複数ある場合は１番目と同じ値が格納される場合があります。これは考えすぎかもしれません。

　とりあえずソートしないでも同じことは出来ますので参考までにサンプルを付けます。
　【サンプル】
　アルゴリズム：n回ループして最大値とその次の値を保存していきます。

int E[n]; // 要素配列 n個
int max1st = INT_MIN; // 最大値 初期値としてint型の最小値を設定
int max2nd = INT_MIN; // 最大値の次の値 初期値としてint型の最小値を設定
int i; // ループ用

for ( i = 0; i < n; i++ ) {
if ( E[i] > max1st ) { // 最大値よりE[i]が大きい場合は最大値を更新
max2nd = max1st; // 2番目は旧最大値
max1st = E[i]; // 最大値の更新
} else if ( ( max1st > E[i] ) && ( E[i] > max2nd ) ) { // 最大値ではないが2番目かも(max1st > E[i] > max2dの場合は更新)
max2nd = E[i]; // 2番目の最大値更新
}
}

/* 答えはmax2ndに格納されます。見つからない場合はINT_MINが格納されます。 */

回答No.4

chie65536（@chie65535）

＞これであっていますでしょうか？
あってません。

配列を並び替える必要はありません。

int main(void)
{
int E[10]={67,-4,2,66,22,-5,65,3,0,-55};
int i,i1,i2;
i1=0;
i2=-1;
for (i = 1;i <= 9;i++) {
if (E[i1] < E[i]) i1 = i;
}
for (i = 0;i <= 9;i++) {
if (E[i1] < E[i]) i1 = i;
if (E[i1] > E[i]) {
if (i2 != -1) {
if (E[i2] < E[i]) i2 = i;
} else i2 = i;
}
}
printf("%d\n",E[i2]);
}

ANo.2の回答者さんへ
＞一重ループで処理することを考えてください。
やってみれば判りますが、単純な１重ループでは実現できません。

＞以上のようにすれば E(imax),E(inext)に最大値、二番目のものが求まる
求まりません。
ANo.2の回答者さんのアルゴリズムではimaxとinextの両方が0のままループを終了する可能性があります。

回答No.3

cistronezk

＞アルゴリズムとしては、まず、n-1回の比較をしてその中でmaxを見つけ、残りのn-1個の要素のなかでn-2回の比較をしてそのn-1個の配列のmaxを見つければ、２番目に大きい要素を見つけられると考えました。

最大値が複数ある場合への対応が抜け落ちているようです。
「n-1回の比較をしてその中でmaxを見つけ、またn-1回の比較をして最初のmax以外のmaxを見つける」
となると思います。

しかし、コードはもっとおかしいと思います。ちなみにコードはコンパイルが通るものを提示していただきたいですね。
初期化されていない変数ｎを使って
＞int E[n];
とか、いただけない。配列Ｅを初期化せず参照していることも同様。
それと"n"と"N"は違います。

文章では、(n-1)+(n-2)回ループすると書いてあるのに、n(n-1)/2回も回しているのはなぜ？forをネストするのではなく、別々に２回書くべきでは？
コードの中では最初のｍａｘを除いた比較もしていません。

int E[]={1,2,3,4,4};
とか小さい配列の例をいくつか実際に動作確認することを薦めます。
アルゴリズムはいろいろあるでしょうが、ご自分の考えをきちっとコードに表わせるようになるためにも大切なことです。

回答No.2

ninoue

あっているとは思われます。
但しもっと良いやりかたがあると思われます。
まずこのやり方では内部ループの実行回数がn*n/2のオーダー実行されます。
それとアレイEはメモリ参照のみで処理できると思われます。
(メモリストアは参照よりも実行時間がかかりますので)

一重ループで処理することを考えてください。

一番、二番目に大きい数のindex:imax,inextを0に初期化する
for(i=1;i<n;i++) {
if(E(i)<=E(inext)) continue;
if (E(i)>E(imax) {...}
else {...}
}

以上のようにすれば E(imax),E(inext)に最大値、二番目のものが求まるように出来るはずですので検討してください。

回答No.1

asuncion

＞n個の要素をもった配列で、２番目に大きい要素を見つけるコード

既存のソートアルゴリズムのいずれかを用いて、
与えられた配列を降順にソートします。

このとき、いちばん大きい値が配列の[0]に入っていますね。
そして、2番目に大きい要素が配列の[1]に入っています。