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. Runtime: 8 ms, faster than 85.71% of C++ online submissions for Third Maximum Number.

    1. class Solution {
    2. public:
    3.     int thirdMax(vector<int>& nums) {
    4.         int size = nums.size();
    5.         if (size < 2) {
    6.             return nums[0];
    7.         }
    8.         if (size < 3) {
    9.             return max(nums[0], nums[1]);
    10.         }
    11.         int nth = 0;
    12.         for (int i = 0; i < size; i++) {
    13.             int idx = size - i - 1;
    14.             for (int j = 0; j < idx; j++) {
    15.                 if (nums[j + 1] < nums[j]) {
    16.                     int temp = nums[j];
    17.                     nums[j] = nums[j + 1];
    18.                     nums[j + 1] = temp;
    19.                 }
    20.             }
    21.             if (i == 0) {
    22.                 nth++;
    23.             } else if (nums[idx] < nums[idx + 1]) {
    24.                 nth++;
    25.             }
    26.             if (nth == 3) {
    27.                 return nums[idx];
    28.             }
    29.         }
    30.         return nums[size - 1];
    31.     }
    32. };