leetcode解题报告（15）：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.
分析
强行用map写出来的，很粗暴的解法：
将nums的元素都放到map中，map的key是元素值，value是元素个数，放进去后map也被顺序排序好了。
如果排序后的元素个数大于等于3，那么第三大的元素就是map的最后一个迭代器减去3（map.end()指向的是尾后元素），如果小于3，返回最后一个元素即可。
代码如下：
class Solution {
public:
int thirdMax(vector<int>& nums) {
if(nums.size() == 0)return 0;
map<int,int>m;
for(int num : nums)
++m[num];
if(m.size() == 1) return m.begin()->first;
else if(m.size() == 2) return m.rbegin()->first;
else{
auto ret = m.rbegin();
++ret;
++ret;
return ret->first;
}
}
};
在讨论区看到了一个用set解的，不过我的时间复杂度应该比这个更低: )
https://discuss.leetcode.com/topic/63903/short-easy-c-using-set
class Solution {
public:
int thirdMax(vector<int>& nums) {
set<int>top3;
for(int num : nums){
top3.insert(num);
if(top3.size() > 3)top3.erase(top3.begin());
}
return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
}
};
最新文章
- 2DToolkit官方文档中文版打地鼠教程（二）：设置摄像机
- android第一行代码－3.activity之间的调用跟数据传递
- JSONObject put,accumulate,element的区别
- 如何让nginx显示文件夹目录
- webstorm 运行配置gulp
- myeclipse2015CI Server显示derby服务器去除方法
- NYOJ题目1162数字
- JS设计模式一：单例模式
- Web Service 性能测试工具比较
- 国内最快的jquery cdn
- MySql join on 和 where
- NSAttributedString富文本简单介绍和常用方法浅析
- Ubuntu安装守护进程supervisor
- “==”运算符与equals()
- （转）c#反射
- js函数定义和调用
- 014_mac下的端口查看
- 【硅谷问道】Chris Lattner 访谈录（下）
- 解决web翻转动画闪屏
- 将Gradle项目公布到maven仓库