414. Third Maximum Number -E

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;
    }
};