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

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

解题思路：
设置最大、第二大、第三大的变量，遍历数组，更新这三个变量，考虑相同的数字时，变更三个变量的策略。

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long first_max = LONG_MIN;
        long second_max = LONG_MIN;
        long third_max = LONG_MIN;

        for (auto num : nums) {
            if (num > first_max) {
                if (second_max != LONG_MIN) third_max = second_max;
                if (first_max != LONG_MIN) second_max = first_max;
                first_max = num;
            }
            else if (num > second_max && num != first_max) {
                if (second_max != LONG_MIN) third_max = second_max;
                second_max = num;
            }
            else if (num > third_max && num != second_max && num != first_max) 
                third_max = num;
        }

        return third_max == LONG_MIN ? first_max : third_max;
    }
};

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!