本文共 1955 字，大约阅读时间需要 6 分钟。

题目

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.

解答

这一题看着简单，其实不是那么容易AC的。主要是需要对一些特殊的输入进行特殊处理。

注意：[2,1,1]这种情况是不存在第三大的，返回2。

用三个变量first,second,third来表示第一大，第二大，第三大。

用count来表示这三个更新次数。如果更新次数大于等于3，直接返回third。 如果小于3，那就是返回最大值。 但是有一个特殊的例子： [2,1,-2147483648]，这个在判断第三个时是不更新的，所以额外对其进行计数，用bottom来计数，在最后的判断中就用count+bottom来判断。 AC代码：9ms

class Solution {public:    int thirdMax(vector
   
    & nums) {        #define INT_MIN (-2147483647-1)        int max_3[3];        if(nums.size()==1) return nums[0];        else if(nums.size()==2) return nums[1]>nums[0]?nums[1]:nums[0];        else        {            int first=INT_MIN,second=INT_MIN,third=INT_MIN;            bool flag1=0,flag2=0,flag3=0;//是否顶替掉初值            int count=0;            int bottom=0;            //缺少对三个一样的进行判断            for(int i=0;i
    
     first)                {                    third=second;                    second=first;                    first=nums[i];                    count++;                }                else if(nums[i]>second)                {                    third=second;                    second=nums[i];                    count++;                }                else if(nums[i]>third)                {                    third=nums[i];                    count++;                }            }            if(count+bottom>=3)//                 return third;//三个都更新了            else                 return first;//两个更新，一个更新或者都没更新，没达到要求，返回第一个值        }    }};
    
   

转载地址：http://bexvi.baihongyu.com/