Sponsored
This approach involves first sorting the array and then selecting distinct maximums from the sorted array. We can use a set to easily manage distinct elements. After constructing a set, we check if the size of the set is at least 3; if so, we find the third largest by accessing the sorted array of distinct elements, otherwise, return the maximum element.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) as sorting is done in place with qsort.
1#include <iostream>
2#include <vector>
3#include <set>
4
5int thirdMax(std::vector<int>& nums) {
6 std::set<int> distinctSet(nums.begin(), nums.end());
7 if (distinctSet.size() < 3) return *distinctSet.rbegin();
8 for (int i = 0; i < 2; ++i) distinctSet.erase(--distinctSet.end());
9 return *distinctSet.rbegin();
10}
11
12int main() {
13 std::vector<int> nums = {2, 2, 3, 1};
14 std::cout << thirdMax(nums) << std::endl;
15 return 0;
16}In the C++ solution, we use a set to handle distinct elements and order them automatically. If the size of the set is less than 3, we return the maximum number (last element). Otherwise, we remove the top two maximum numbers and return the third maximum by accessing the last element of the set.
This approach keeps track of the three largest distinct numbers iteratively as it processes the array. It uses variables to track them and updates them as it iterates through each number. This way, it can achieve O(n) time complexity without additional set or sorting overhead.
Time Complexity: O(n) because it performs a single pass over the array.
Space Complexity: O(1) as only constant space is used for tracking the maximums.
1
In JavaScript, we check three variables for greatest distinct values iteratively, familiarizing the logic by array destructuring assignments for maintaining and updating positional integer states. Returns are accordingly based on the presence of a valid third distinct found in traversal.