414. Third Maximum Number

题目

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

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

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

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.

解法

用m1、m2、m3分别来存放最大、第二大、第三大，遍历数组，比较大小。注意这里需要剔除重复元素，如果遇到m1、m2、m3中已经有的元素就不需要再比较大小了，直接下一个。

class Solution { public: int thirdMax(vector<int>& nums) { long long m=LLONG_MIN; long long m1=m,m2=m,m3=m; for(int i=0;i<nums.size();i++){ if(nums[i]==m1 || nums[i]==m2 || nums[i]==m3) continue; if(nums[i]>m1){ m3=m2; m2=m1; m1=nums[i]; } else if(nums[i]>m2){ m3=m2; m2=nums[i]; } else if(nums[i]>m3){ m3=nums[i]; } } if(m3==m) return m1; else return m3; } };

经验

第一次写的时候用的是int

int m=INT_MIN;

结果，有一条测试没通过，哈哈哈。预期是-2147483648，结果输出是2，因为INT_MIN被当成重复元素剔除了。

[1,2,-2147483648]

改成long或者long long（C++11）就好了。