C++ में तीसरा अधिकतम नंबर

समस्या विवरण

मान लीजिए हमारे पास पूर्णांकों की एक गैर-खाली सरणी है; हमें इस सरणी में तीसरा अधिकतम नंबर ज्ञात करना है। यदि तीसरा अधिकतम नंबर नहीं है, तो अधिकतम नंबर लौटाएं। चुनौती यह है कि हमें इसे रैखिक समय जटिलता में हल करना है।

उदाहरण

यदि इनपुट है: [5,3,8,9,1,4,6,2], तो आउटपुट होगा 6।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:

a, b, c को NULL से आरंभ करें
i := 0 से आरंभ करें, जब i < 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 का मान)

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

int main() {
    Solution ob;
    vector<int> v = {5,3,8,9,1,4,6,2};
    cout << (ob.thirdMax(v));
    return 0;
}

इनपुट

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