LeetCode 414. Third Maximum Number

414. Third Maximum Number

Total Accepted: 22549
Total Submissions: 83903
Difficulty: Easy
Contributors: ZengRed , 1337c0d3r

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.

Subscribe to see which companies asked this question.

【题目分析】

给定一个整数数组，返回数组中第三大的数，如果该数不存在，则返回最大的那个数。要求时间复杂度为O(n).

【思路分析】

1. 找到最大的数和最小的数

2. 遍历数组，找到次小的数

3. 如果次小的数存在，再次遍历数组找到第三小的数。

【java代码】

 1 public class Solution {
 2     public int thirdMax(int[] nums) {
 3         if(nums.length == 1) return nums[0];
 4         if(nums.length == 2) 
 5             return nums[0] > nums[1] ? nums[0] : nums[1];
 6         
 7         int firstmax = nums[0];
 8         int firstmin = nums[0];
 9         for(int i = 1; i < nums.length; i++) {
10             firstmax = Math.max(firstmax, nums[i]);
11             firstmin = Math.min(firstmin, nums[i]);
12         }
13         
14         int secondmax = firstmin;
15         for(int i = 0; i < nums.length; i++) {
16             if(nums[i] < firstmax)
17                 secondmax = Math.max(secondmax, nums[i]);
18         }
19         
20         if(secondmax < firstmax) {
21             int thirdmax = firstmin;
22             for(int i = 0; i < nums.length; i++) {
23                 if(nums[i] < secondmax)
24                     thirdmax = Math.max(thirdmax, nums[i]);
25             }
26             if(thirdmax < secondmax) return thirdmax;
27         }
28         return firstmax;
29     }
30 }

上述代码的缺点是每次遍历时要先确定一个下届，因此必须先找到数组中最小的那个值。但是算法的时间效率还是不错的。一个更加简明的程序如下：

 1 public int thirdMax(int[] nums) {
 2         Integer max1 = null;
 3         Integer max2 = null;
 4         Integer max3 = null;
 5         for (Integer n : nums) {
 6             if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
 7             if (max1 == null || n > max1) {
 8                 max3 = max2;
 9                 max2 = max1;
10                 max1 = n;
11             } else if (max2 == null || n > max2) {
12                 max3 = max2;
13                 max2 = n;
14             } else if (max3 == null || n > max3) {
15                 max3 = n;
16             }
17         }
18         return max3 == null ? max1 : max3;
19     }