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

题目大意

  给定一个数组,找到第三大的数字。

  要求:没有第三大的数字返回最大的数字。两数值相等时同样大。且时间复杂度O(n)以内。

理  解:

  用set存放数据,不出现重复的数字。且内部从小到大排序。set大小小于3,则返回最大的数。set大小大于等于3,则返回倒数第三个数。

  或者 : 直接遍历保存第一、第二、第三大的数。

代 码 C++:

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> sortNums(nums.begin(),nums.end());
        set<int>::iterator itr = sortNums.end();
        
        if(sortNums.size()<3)
            return *prev(itr,1);
        else
            return *prev(itr,3);
    }
};

运行结果:

  执行用时 :20 ms, 在所有 C++ 提交中击败了35.10%的用户

  内存消耗 :10.4 MB, 在所有 C++ 提交中击败了19.73%的用户
上一篇:异步 IO(Asynchronous IO)


下一篇:图像显示