414. 第三大的数

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个非空数组，返回此数组中第三大的数。 如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是\(O(n)\)​。

示例 1: >输入: [3, 2, 1] >输出: 1 >解释: 第三大的数是 1.

示例 2: >输入: [1, 2] >输出: 2 >解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3: >输入: [2, 2, 3, 1] >输出: 1 >解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 >存在两个值为2的数，它们都排第二。

提示：

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

代码

\(T(N) = O(N)\), \(S(N) = O(1)\)

{.line-numbers}
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
class Solution414 
{
    public int thirdMax(int[] nums) 
	{
		// 注意必须要用Long的MIN而不是Integer的MIN
    	long max1 = Long.MIN_VALUE;
    	long max2 = Long.MIN_VALUE;
    	long max3 = Long.MIN_VALUE;
    	
    	for (int i=0; i<nums.length; i++)
    	{
			// 避免重复元素占位置
    		if (nums[i]==max1||nums[i]==max2||nums[i]==max3) continue;

    		if (nums[i]>max1)
    		{
    			max3 = max2;
    			max2 = max1;
    			max1 = nums[i];
    		}
    		else if (nums[i]>max2)
    		{
    			max3 = max2;
    			max2 = nums[i];
    		}
    		else if (nums[i]>max3)
    			max3 = nums[i];
    	}
    	
		// 不够三个元素的情况
    	if (max3==Long.MIN_VALUE) return (int)max1;
    	
    	return (int)max3;
    }
}