Số tối đa thứ ba trong C ++

Giả sử chúng ta có một mảng các số nguyên không rỗng; chúng ta phải tìm số lớn nhất thứ ba trong mảng này. Nếu không có số tối đa thứ 3, thì trả về số lớn nhất. Thách thức là, chúng ta phải giải quyết vấn đề này bằng cách sử dụng độ phức tạp thời gian tuyến tính.

Vì vậy, nếu đầu vào là [5,3,8,9,1,4,6,2], thì đầu ra sẽ là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

khởi tạo a, b, c bằng NULL
để khởi tạo i:=0, khi tôi
- nếu a là null hoặc nums [i]> =giá trị của a thì -
  - nếu không phải là giá trị null và nums [i]> của a thì -
    - c:=b, b:=a
  - a:=nums [i]
- ngược lại khi b là null hoặc nums [i]> =giá trị của b thì -
  - nếu b không null và nums [i]> giá trị của b thì -
    - c:=b
  - b:=nums [i]
- ngược lại khi c là null hoặc nums [i]> =giá trị của c thì -
  - c:=nums [i]
return (nếu c là null thì giá trị của a, nếu không thì giá trị của c)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Số tối đa thứ ba trong C ++

Ví dụ

Đầu vào

Đầu ra