C ++中的第三最大数

假设我们有一个非空的整数数组；我们必须在此数组中找到第三个最大数字。如果没有第三个最大数字，则返回最大一个。挑战在于，我们必须使用线性时间复杂度来解决这个问题。

因此，如果输入类似于[5,3,8,9,1,4,6,2]，则输出将为6。

为了解决这个问题，我们将遵循以下步骤-

• 用NULL初始化a，b，c

• 对于初始化i：= 0，当i <nums大小时，更新（将i增加1），执行-

• c：= nums [i]

• 如果b不为null并且nums [i]> b的值，则-

• b：= nums [i]

• c：= b

• 如果不为null并且nums [i]> a的值，则-

• a：= nums [i]

• c：= b，b：= a

• 如果a为null或nums [i]> = a的值，则-

• 否则，当b为null或nums [i]> = b的值时，则-

• 否则，当c为null或nums [i]> = c的值时，则-

• 返回（如果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