p414

发表于 | 分类于 |

LeetCode p414 Third Maximum Number 题解

1.题目：

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:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
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.

题意：

输入一个数组，输出其中第三大的数。
重复的数并列
没有第三大的数，则输出最大的数

2.解题思路:

见代码
注意类型orz
我开始时用int型初始化为虽小值的。。然后测试数据里面有Integer.MIN_VALUE的值。。
//其实也可以flag标记解决

3.代码

[title] [] [url] [link text]
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
 
public class Solution {
    public int thirdMax(int[] nums) {
        Integer max1 = null;
		Integer max2 = null;
		Integer max3 = null;
		for (int i = 0; i < nums.length; i++) {
			Integer k = nums[i];
			if (k.equals(max1) || k.equals(max2) || k.equals(max3))
				continue;
			if (max1 == null || k > max1) {
				max3 = max2;
				max2 = max1;
				max1 = k;
				// System.out.println(max1+"  "+max2+" "+max3);
				continue;
			}
			if (max2 == null || k > max2) {
				max3 = max2;
				max2 = k;
				continue;
			}
			if (max3 == null || k > max3) {
				max3 = k;
				continue;
			}

		}
		if (max3 == null)
			return max1;
		// return max2 == Integer.MIN_VALUE ? max1 : max2;
		return max3;
    }
}

4.一些总结：