博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode] Third Maximum Number 第三大的数
阅读量:6205 次
发布时间:2019-06-21

本文共 2087 字,大约阅读时间需要 6 分钟。

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: 1Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]Output: 2Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]Output: 1Explanation: Note that the third maximum here means the third maximum distinct number.Both numbers with value 2 are both considered as second maximum.

这道题让我们求数组中第三大的数,如果不存在的话那么就返回最大的数,题目中说明了这里的第三大不能和第二大相同,必须是严格的小于,而并非小于等于。这道题并不是很难,如果知道怎么求第二大的数,那么求第三大的数的思路都是一样的。那么我们用三个变量first, second, third来分别保存第一大,第二大,和第三大的数,然后我们遍历数组,如果遍历到的数字大于当前第一大的数first,那么三个变量各自错位赋值,如果当前数字大于second,小于first,那么就更新second和third,如果当前数字大于third,小于second,那就只更新third,注意这里有个坑,就是初始化要用长整型long的最小值,否则当数组中有INT_MIN存在时,程序就不知道该返回INT_MIN还是最大值first了,参见代码如下:

解法一:

class Solution {public:    int thirdMax(vector
& nums) { long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN; for (int num : nums) { if (num > first) { third = second; second = first; first = num; } else if (num > second && num < first) { third = second; second = num; } else if (num > third && num < second) { third = num; } } return (third == LONG_MIN || third == second) ? first : third; }};

下面这种方法的时间复杂度是O(nlgn),不符合题目要求,纯粹是拓宽下思路哈,利用了set的自动排序和自动去重复项的特性,很好的解决了问题,对于遍历到的数字,加入set中,重复项就自动去掉了,如果此时set大小大于3个了,那么我们把set的第一个元素去掉,也就是将第四大的数字去掉,那么就可以看出set始终维护的是最大的三个不同的数字,最后遍历结束后,我们看set的大小是否为3,是的话就返回首元素,不是的话就返回尾元素,参见代码如下:

解法二:

class Solution {public:    int thirdMax(vector
& nums) { set
s; for (int num : nums) { s.insert(num); if (s.size() > 3) { s.erase(s.begin()); } } return s.size() == 3 ? *s.begin() : *s.rbegin(); }};

本文转自博客园Grandyang的博客,原文链接:,如需转载请自行联系原博主。

你可能感兴趣的文章
Revel运行APP出现的路径问题
查看>>
android studio :cannot resolve symbol R
查看>>
paper 20 :color moments
查看>>
绘图笔记
查看>>
代码大全
查看>>
博客园作业4--数组
查看>>
DataTable.ImportRow()与DataTable.Rows.Add()的区别
查看>>
微信小程序左右滑动切换页面示例代码--转载
查看>>
C2 shell
查看>>
【jQuery】关于选择器中的 :first 、 :first-child 、 :first-of-type
查看>>
dom 解析xml文件
查看>>
程序集、应用程序配置及App.config和YourSoft.exe.config .
查看>>
二叉树的基本操作及应用(三)
查看>>
A SimpleDataStore
查看>>
朱晔和你聊Spring系列S1E3:Spring咖啡罐里的豆子
查看>>
IOS CALayer的属性和使用
查看>>
温故而知新:柯里化 与 bind() 的认知
查看>>
查看修改swap空间大小
查看>>
Django REST framework
查看>>
出了本练内功的书:《完美软件开发:方法与逻辑》
查看>>