空間と時間の両方の複雑さの点で最も効率的な方法で配列の 2 番目の最大値を見つけようとしていますが、2つの大きな問題があります。
単純なまたは力ずくのアプローチでは、最小の要素を見つけるために 2 つのパスが必要になるため、O(n) の複雑さになります。配列を並べ替えると、O(n 2 ) かかります。
O(log(n)) ソートにはいつでも BST を使用できますが、ツリーを維持するために追加のスペースが必要になります。ヒープを作成して 2 つの削除を行うこともでき、2 番目に大きい要素を取得できますが、ここでもヒープが作成され、メモリに格納されます。
ここにはどのようなオプションがありますか?
これを 1 回のパスで実行できます。max と 2nd max の 2 つの変数を保持するだけです。最大値を更新するたびに、古い最大値が新しい第 2 の最大値になります。
kこれは、 1 つのパスと O(k) スペースを使用して最大 (または最小) の要素を見つけることができる Top-k アルゴリズムに一般化されます。あなたの場合k=2。
リスト内で n 番目に大きい項目を見つけることは選択問題と呼ばれ、それを解くための多くのアルゴリズムがあります。http://en.wikipedia.org/wiki/Selection_algorithm
リストのすべての項目を少なくとも 1 回確認する必要があるため、達成できる最小の複雑さは O(n) です。たとえば、n 個のリストから上位 k 個の項目を見つけることは、部分挿入ソートを使用して O(kn) 時間で実行できます (リストをウォークスルーし、上位 k 個の要素を追跡します)。
k に関係なく、O(n) 時間で上位 k 個のアイテムを見つける quickselect というアルゴリズムがあります。調べることをお勧めしますが、トップ 2 を見つけるには、リストを 1 回スキャンする単純な方法で十分です。