Second Largest Number

コピーを小さい順に並べ替えます。最大値は末尾にあり、連続して複数回現れることもあります。末尾から左へ向かって最大値と同じ値をすべて通り過ぎると、最初に見つかる異なる値が2番目に大きい値です。[6, 6, 6, 3]の場合、並べ替えたコピーは[3, 6, 6, 6]です。6を3つ通り過ぎて、3にたどり着きます。

ここでよくある間違いは、後ろから2番目の要素を返すことです。[4, 9, 2, 7, 9]の場合、それでは最大値と同じ9が返されます。リストには少なくとも2つの異なる値が含まれているため、走査が先頭を通り越すことはありません。

答えは正しいものの、上位2つだけが必要なのに、並べ替えではすべての値を順序付けます。時間計算量はO(n log n)で、コピーにはO(n)のメモリが必要です。

処理を2回に分けます。1回目の走査では、「最大の数を見つける」と同じように最大値を見つけます。2回目の走査では、その最大値より厳密に小さい値のうち、最も大きいものを探します。[4, 9, 2, 7, 9]の場合、1回目の走査で9が見つかり、2回目の走査では2つの9を飛ばして、4、2、7の中で最も大きい7を保持します。

secondは、リストに入る可能性のあるすべての値より小さい値（たとえば、その言語で扱える最小の整数）で初期化します。リストには少なくとも2つの異なる値があるため、最大値より小さい値があり、必ずその初期値が置き換えられます。

それぞれの走査では最大値を更新していくため、全体の計算量は時間がO(n)、空間がO(1)です。ただし、リストを2回読み取る必要があります。そのため、値が1つずつ届き、読み取った後に失われる場合には、この方法は使えません。

これまでに見た値のうち、大きい順に上位2つの異なる値を保持するため、largestとsecondの2つの変数を使います。新しい値xは、次の3つのケースのいずれかに当てはまります。xがlargestより大きければ、以前のlargestが2番目になり、xが最大の値になります。xがsecondとlargestの間に厳密に位置する場合、新しいsecondになります。それ以外の場合は何も変わりません。

重複を処理するのは、厳密な比較です。[4, 9, 2, 7, 9]の場合、largestは4になり、次にsecond = 4として9になります。2では何も変わりません。7は4と9の間にあるため、second = 7となります。最後の9はlargestと等しいため、スキップされます。答えは7です。

両方の変数を、あり得るすべての値より小さい値で初期化します。両方を0で初期化すると、どの値も0を上回らないため、[-5, -1, -8]に対して0が返されます。リストには異なる値が2つ含まれているため、最終的にsecondには必ずリスト内の実際の値が入ります。