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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int *)b - *(int *)a);
6}
7
8int thirdMax(int* nums, int numsSize) {
9 qsort(nums, numsSize, sizeof(int), compare);
10 int distinctCount = 1;
11 int currentMax = nums[0];
12 for (int i = 1; i < numsSize; i++) {
13 if (nums[i] != currentMax) {
14 distinctCount++;
15 currentMax = nums[i];
16 if (distinctCount == 3) {
17 return nums[i];
18 }
19 }
20 }
21 return nums[0];
22}
23
24int main() {
25 int nums[] = {2, 2, 3, 1};
26 int size = sizeof(nums) / sizeof(nums[0]);
27 printf("%d\n", thirdMax(nums, size));
28 return 0;
29}This C solution uses the C standard library function qsort to sort the array in descending order. We then traverse the sorted array to count distinct elements. We track the number of distinct numbers found and when the count reaches three, we return the number. If we pass through the entire array without finding three distinct maximums, we return the first number.
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
Python uses negative infinity for initial state and efficiently updates first, second, and third variables akin to the logic of replacing as larger numbers are encountered in a single pass of the list. The third result reflects any real third distinct maximum conditionally discovered as the list was traversed.