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.
A:
class Solution { public: int thirdMax(vector<int>& nums) { int a1, a2, a3; a1 = nums[0]; bool find2 = false, find3 = false; for(int i =1;i<nums.size(); ++i) { int b = nums[i]; if(b== a1) continue; if(b>a1){ int c = a1; a1=b; b=c; } // now compare with 2nd if(not find2){ find2 = true; a2 = b; }else{ if(b == a2) continue; if(b > a2){ int c = a2; a2=b; b=c; } // now b < a2, compare with a3 if(not find3){ find3 = true; a3=b; }else{ a3 = max(a3,b); } } } return find3?a3:a1; } };
No comments:
Post a Comment