2番目に高い要素

Question

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

Answer 1

どちらも、率直に。配列を並べ替えるのは、せいぜい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; 
} 

Answer 2

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

Answer 3

：

は、以下（例えば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