C++의 세 번째 최대 수

<시간/>

비어 있지 않은 정수 배열이 있다고 가정합니다. 이 배열에서 세 번째 최대값을 찾아야 합니다. 세 번째 최대 숫자가 없으면 최대 숫자를 반환합니다. 문제는 선형 시간 복잡도를 사용하여 이 문제를 해결해야 한다는 것입니다.

따라서 입력이 [5,3,8,9,1,4,6,2]와 같으면 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

NULL로 a, b, c 초기화
initialize i :=0의 경우, i
- a가 null이거나 nums[i]>=a의 값이면 -
  - null이 아니고 nums[i]> a의 값이면 -
    - c :=b, b :=a
  - a :=숫자[i]
- 그렇지 않으면 b가 null이거나 nums[i]>=b의 값이면 -
  - b가 null이 아니고 nums[i]> b의 값이면 -
    - c :=b
  - b :=숫자[i]
- 그렇지 않으면 c가 null이거나 nums[i]>=c의 값이면 -
  - c :=숫자[i]
반환(c가 null이면 값, 그렇지 않으면 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}