自己的做法
算法思想
定义三个变量：max、second_max、third_max，首先遍历数组，找出最大的数。
然后再次遍历数组，但注意：只有当该数不等于max时，才进行下一步操作，找出第二大的数second_max。
然后再次遍历数组，同样：只有当该数不等于max和second_max时，才进行下一步操作，找出第三大的数third_max。
返回即可。
注：
- 定义一个标志变量
init_status来标识 表示second_max和third_max是否被改变了初始值。 - 在找到最大值之后，second_max 和 third_max应被初始为最大值max。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
static int thirdMax(vector<int>& nums) {
if(nums.size() == 1) {
return nums[0];
} else if(nums.size() == 2) {
return nums[0] > nums[1] ? nums[0] : nums[1];
}
int max = nums[0], second_max = 0, third_max = 0;
bool init_status = true;
int length = nums.size();
for (int i = 0; i < length; ++i) {
if(max < nums[i]) {
max = nums[i];
}
}
second_max = max;
third_max = max;
for(int i = 0; i < length; ++i) {
if(nums[i] != max) {
if(init_status) {
second_max = nums[i];
init_status = false;
}
if(second_max < nums[i]) {
second_max = nums[i];
}
}
}
init_status = true;
for (int i = 0; i < length; ++i) {
if(nums[i] != max && nums[i] != second_max) {
if(init_status) {
third_max = nums[i];
init_status = false;
}
if(nums[i] > third_max) {
third_max = nums[i];
}
}
}
return third_max;
}
};
|
注：代码很垃圾，又丑又长，但我实在没啥子好方法。
性能分析
时间复杂度：一共遍历了五遍数组，为O(n)。
空间复杂度：使用了四个变量，O(1)。
没有官方题解。