首页 > 代码库 > Leetcode-414 Third Maximum Number
Leetcode-414 Third Maximum Number
#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.
题解:这道题要找到第三大的数,我用了set,避免同一元素出现多次,定义反向迭代器,之后判断set中有多少个元素,小于三个时直接返回最大值,否则反向迭代就可以找到第三大的值了,时间复杂度是O(n)
class Solution { public: int thirdMax(vector<int>& nums) { set<int> num; for(int i=0;i<nums.size();i++) { num.insert(nums[i]); } set<int>::reverse_iterator it=num.rbegin(); if(num.size()<3) return *it; it++; it++; return *it; } };
Leetcode-414 Third Maximum Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。