JavaScriptで配列内の3番目に大きい数値を求める方法

問題の概要

数値が格納された配列を受け取り、その中から3番目に大きい数値を取り出して返すJavaScript関数を作成します。

ただし、関数の時間計算量はO(n)以内に収める必要があります。つまり、sort()などで配列を並べ替えることなく、たった1回のループ処理で目的の数値を見つけなければなりません。

解決アプローチ

最も効率的なのは、上位3つの値を保持する変数を用意し、配列を1周しながら順次更新していく手法です。具体的な手順は以下の通りです。

• first（最大値）、second（2番目）、third（3番目）をすべて -Infinity で初期化します。
• 各要素がすでに保持している3つの値のいずれかと重複している場合はスキップします（重複値を除外するため）。
• 要素が first より大きければ、3つの変数を1つずつ後ろへずらして更新します。
• 要素が second より大きければ、second と third を更新します。
• 要素が third より大きければ、third だけを更新します。

ループ終了後、third が初期値のまま（有効な3番目の値が存在しない場合）であれば、代わりに first を返します。これにより、計算量O(n)・単一パスという要件を満たせます。

コード例

const arr = [1, 5, 23, 3, 676, 4, 35, 4, 2];
const findThirdMax = (arr) => {
  let [first, second, third] = [-Infinity, -Infinity, -Infinity];
  for (let el of arr) {
    if (el === first || el === second || el === third) {
      continue;
    }
    if (el > first) {
      [first, second, third] = [el, first, second];
      continue;
    }
    if (el > second) {
      [second, third] = [el, second];
      continue;
    }
    if (el > third) {
      third = el;
      continue;
    }
  }
  return third !== -Infinity ? third : first;
};
console.log(findThirdMax(arr));

出力結果

コンソールには以下のように表示されます。

23