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.
1import java.util.TreeSet;
2
3public class Solution {
4 public int thirdMax(int[] nums) {
5 TreeSet<Integer> distinctSet = new TreeSet<>();
6 for (int num : nums) {
7 distinctSet.add(num);
8 if (distinctSet.size() > 3) {
9 distinctSet.pollFirst();
10 }
11 }
12 return distinctSet.size() < 3 ? distinctSet.last() : distinctSet.first();
13 }
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] nums = {2, 2, 3, 1};
17 System.out.println(sol.thirdMax(nums));
18 }
19}This Java solution leverages the TreeSet to maintain a sorted order of unique elements. It iterates over the array, inserting elements into the set. If the size exceeds three, it removes the smallest element. At the end, if the set size is less than three, it returns the largest element. Otherwise, it returns the smallest element available which represents the third maximum.
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
This C solution uses additional variables (initialized to the smallest possible value using LONG_MIN) to track the first, second, and third maximum numbers. During the iteration, if the current number doesn't match the tracked maximums, it updates the respective maximum. At the end of the loop, it checks if the third max was updated from its initialized state, returning it only if so; otherwise, it returns the first maximum.