2番目に高い要素

-2

配列の2番目に高い要素を見つけるには、配列全体をソートして（バブルソート）、次にソートされた配列の2番目に高い要素を出力する方がいいですか？最も高い要素（2番目に高い要素）を再度見つけますか？2番目に高い要素

2016-06-26 floralmural

最初のオプションが良いです。 'Array.sort'を使って2番目の要素を表示してください。また、必要な情報を提供してください。 – Rajesh

最高のものを見つけたほうがいいですし、2番目に高いのが良いです。なぜなら、 'n（n）'のマージソート（または一般的に使われるクイックソート）と比較して 'O（n） 'しかないからです。 –

次の記事を参照してください。http://stackoverflow.com/questions/2615712/finding-the-second-highest-number-in-array – Rajesh

どちらも、率直に。配列を並べ替えるのは、せいぜいO（nlog（n））の操作だけです（バブルソートを使わないでください！）。配列を2回移動することは、O（n）操作ですが、実行時間の約半分を節約できます。一度に配列を上書きし、2番目に大きな配列を格納するだけです。それによりワンパスでより効率的に完全に可能である

int secondHighest(int[] arr) { 
    // Assumption: There are at least two elements in the array 
    int highest; 
    int secondHighest; 
    if (arr[0] > arr[1]) { 
     highest = arr[0]; 
     secondHighest = arr[1]; 
    } else { 
     highest = arr[1]; 
     secondHighest = arr[0]; 
    } 

    for (int i = 2; i < arr.length; ++i) { 
     if (arr[i] >= highest) { 
       secondHighest = highest; 
       highest = arr[i]; 
      } else if (arr[i] > secondHighest) { 
       secondHighest = arr[i]; 
      } 
    } 

    return secondHighest; 
}

出典

2016-06-26 04:43:10 Mureinik

あなたが行くにつれて、2つの最も高い要素を追跡しながら、配列を1回通過させる必要があります。

出典

2016-06-26 04:38:23

なぜそれが良いのか、それ以外の理由だけを述べることは良い考えです。 –

私は初心者がbig-Oやメモリ帯域幅ではなく、大丈夫だと仮定しました。ソートは一般にO（N log N）、バブルソートはO（N^2）であり、それを2回実行して、よりキャッシュに優しい方法です。 –

もしそうでなければ、単純にこの方法で効率を上げることができます。なぜなら、並べ替えが複数回繰り返されるうちに、配列を1回だけ/（2回）反復するからです。私は彼らが前にビッグ・オウを見たかもしれないバブル・ソートが何であるかを知っているから考えていました。 –

：

は、以下（例えばintアレイ用のJavaで与えられるが、容易に他の言語またはデータ型に翻訳可能であるべきである）を考えます。 2つの最も高い値を探し、2つ目の値を選択します。

擬似コード

INTEGER FINDSECONDHIGHEST (ARRAY A) 
    INTEGER FIRST = MINIMUM_INTEGER_VALUE_POSSIBLE 
    INTEGER SECOND = MINIMUM_INTEGER_VALUE_POSSIBLE 

    FOREACH INTEGER I IN A 

     IF I > FIRST THEN 

      SECOND = FIRST 
      FIRST = I 

     ELSE IF I > SECOND THEN 

      SECOND = I 

     END IF 

    END FOREACH 

RETURN SECOND

出典

2016-06-26 07:33:27

答えて

関連する問題