LeetCode414 Third Maximum Number

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

样例

1
2
3
4
5
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
1
2
3
4
5
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
1
2
3
4
5
6
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

思路

找出数组中第三小的数。

模拟题。

如果一个数大于当前第一大数,那么更新第一、二、三大数。

如果只大于当前第二大数,那么更新第二、三大数。

如果只大于当前第三大数,那么更新第三大数。

注意相等情况的处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
const long long oo = 1e18;
int thirdMax(vector<int>& nums) {
long long firstNum = -oo, secondNum = -oo, thirdNum = -oo;
for (int& x: nums) {
if (x >= firstNum) { // 等于的情况也要归进来,不然会被拿去更新第二、三大数。
if (x == firstNum) continue;
thirdNum = secondNum;
secondNum = firstNum;
firstNum = x;
} else if (x >= secondNum) {
if (x == secondNum) continue;
thirdNum = secondNum;
secondNum = x;
} else if (x >= thirdNum) thirdNum = x;
}
return (thirdNum == -oo) ? firstNum : thirdNum;
}
};
分享到 评论