C++での3番目の最大数

空でない整数の配列があるとします。この配列で3番目に大きい数を見つける必要があります。 3番目の最大数がない場合は、最大数を返します。課題は、線形時間計算量を使用してこれを解決する必要があることです。

したがって、入力が[5,3,8,9,1,4,6,2]の場合、出力は6になります。

これを解決するには、次の手順に従います-

• a、b、cをNULLで初期化します

• 初期化i：=0の場合、i

  • aがnullまたはnums[i]>=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]

• return（cがnullの場合、aの値、それ以外の場合は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