একটি নন-এমপটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। তৃতীয় সর্বোচ্চ সংখ্যা বের করুন। যদি তৃতীয় সর্বোচ্চ নেই, তবে সর্বোচ্চটি রিটার্ন করুন। লিনিয়ার টাইম কমপ্লেক্সিটিতে সমাধান করতে হবে।
উদাহরণ: [5,3,8,9,1,4,6,2] হলে আউটপুট ৬।
সমাধানের ধাপসমূহ
- তিনটি পয়েন্টার a, b, c NULL দিয়ে আরম্ভ করুন।
- প্রতিটি উপাদানের জন্য:
- যদি a NULL বা nums[i] >= *a: a আপডেট করুন, পুরনো a কে b-তে, b কে c-তে শিফ্ট করুন।
- অন্যথায় যদি b NULL বা nums[i] >= *b: b আপডেট করুন, পুরনো b কে c-তে শিফ্ট করুন।
- অন্যথায় যদি c NULL বা nums[i] >= *c: c আপডেট করুন।
- যদি 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}
আউটপুট
6
