414. Third Maximum Number

Given an integer array `nums`, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example 1:

```Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.
```

Example 2:

```Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.
```

Example 3:

```Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.
```

Constraints:

• `1 <= nums.length <= 104`
• `-231 <= nums[i] <= 231 - 1`
Follow up: Can you find an `O(n)` solution?

Three pointers

Problem Analysis: LeetCode problem 414 “Third Maximum Number” asks us to find the third largest number in an array. If it doesn’t exist, return the largest number. While this could be solved by sorting, we aim for a more efficient approach.

Solution Approach:

1. Use three variables to track the first, second, and third largest numbers.
2. Iterate through the array, updating these variables as needed.
3. Pay attention to duplicates and special cases.

Time and Space Complexity Analysis:

• Time Complexity: O(n), as we only need to pass through the array once.
• Space Complexity: O(1), as we use a fixed amount of extra space.

1. 使用三个变量来追踪第一大、第二大和第三大的数。
2. 遍历数组，更新这三个变量。
3. 注意去重和特殊情况处理。

• 时间复杂度：O(n)，我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只用到有限的额外空间。
``````function thirdMax(nums: number[]): number {
// Initialize three variables to track the largest, second largest, and third largest numbers
let first = Number.MIN_SAFE_INTEGER, second = Number.MIN_SAFE_INTEGER, third = Number.MIN_SAFE_INTEGER;
for (let num of nums) {
// Skip duplicate numbers
if (num === first || num === second || num === third) continue;
if (num > first) { // Update the first, second, and third largest numbers
[third, second, first] = [second, first, num];
} else if (num > second) {
[third, second] = [second, num];
} else if (num > third) {
third = num;
}
}
return third !== Number.MIN_SAFE_INTEGER ? third : first;
}
``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.