C++で3番目に大きい数を求める方法｜O(n)の線形時間アルゴリズム

空でない整数配列が与えられたとき、その中の3番目に大きい数（第3最大値）を求める問題を考えます。第3最大値が存在しない場合は、代わりに最大値を返します。ここでのポイントは、線形時間 O(n) で解く必要があるという点です。

例えば、入力が [5,3,8,9,1,4,6,2] の場合、出力は 6 となります。

解法のアプローチ

この問題は、上位3つの値を常に追跡する変数を用意すれば、配列を一度走査するだけで解けます。手順は以下の通りです。

• 3つのポインタ変数 a、b、c を NULL で初期化します。それぞれ最大値・2番目・3番目に大きい値へのポインタとして機能します。

• i := 0 から配列 nums のサイズ未満の間、i を1ずつ増やしながら次の処理を繰り返します。

  • a が NULL、または nums[i] が a の値以上の場合：

    • a が NULL ではなく、nums[i] が a の値より大きければ、c := b、b := a と順にずらします。

    • a := nums[i] と更新します。

  • そうでなく、b が NULL、または nums[i] が b の値以上の場合：

    • b が NULL ではなく、nums[i] が b の値より大きければ、c := b とします。

    • b := nums[i] と更新します。

  • そうでなく、c が NULL、または nums[i] が c の値以上の場合：

    • c := nums[i] と更新します。

• 最後に、c が NULL なら a の値を、そうでなければ c の値を返します。

計算量

配列を一度だけ走査するため、時間計算量は O(n)、追加の記憶領域も定数 O(1) で済みます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int thirdMax(vector<int>& nums) {
      int *a, *b, *c;
      a = b = c = NULL;
      for (int i = 0; i < nums.size(); ++i) {
         if (!a || nums[i] >= *a) {
            if (a && nums[i] > *a) {
               c = b;
               b = a;
            }
            a = &nums[i];
         }
         else if (!b || nums[i] >= *b) {
            if (b && nums[i] > *b) {
               c = b;
            }
            b = &nums[i];
         }
         else if (!c || nums[i] >= *c) {
            c = &nums[i];
         }
      }
      return !c ? *a : *c;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,8,9,1,4,6,2};
   cout << (ob.thirdMax(v));
}

入力

{5,3,8,9,1,4,6,2}

出力

6