Leetcode Answers 414

又是一道Easy题,和K-th largest有关系,但是比那个简单多了。

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).

Example 1:

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

Example 2:

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

Example 3:

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.

思路:
这里乍一看上去也是K-th largest问题,但是这里首先要求的是distinct number order,其次是O(n) complexity,也就是说,我们只需要遍历一遍找到前三大的数字就好了。理论上只要用int.MinValue来当初始值,最后检查第三大的数字是不是没变就好了,但是一写出来就知道这个不可能,万一就三个数字还都是int.MinValue呢?所以要换个想法,改成用Nullable Type,Nullable,一般缩写成int?,这样可以用null来初始化,然后如果有前三大的数字就赋值,没有就保持null,这样最后如果还是null就返回最大值,不然就返回第三大的值,比再做一个bool[]也省心。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public int ThirdMax(int[] nums) {
int? max1 = null;
int? max2 = null;
int? max3 = null;
int len = nums.Length;
for(int i=0;i<len;i++){
if(max1 == nums[i] || max2 == nums[i] || max3 == nums[i]) continue;
if(max1 == null || nums[i] > max1){
max3 = max2;
max2 = max1;
max1 = nums[i];
}else if(max2 == null || nums[i] > max2){
max3 = max2;
max2 = nums[i];
}else if(max3 == null || nums[i] > max3){
max3 = nums[i];
}
}
return max3 == null ? max1.Value : max3.Value;
}
}

考察:如果是用Java的Integer来写的话,for loop里面的第一个if要用nums[i].Equals(max1),如果直接用==会变成比较引用,而且可能会拆箱失败。

以上。

17-04-27
@Sturbridge

以上。