网站建设对客户的影响,软件开发如何定价,手机制作软件,市辖区郑州网站建设本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个非空数组返回此数组中 第三大的数 。如果不存在则返回数组中最大的数。
示例 1
输入[3, 2, 1]
输出1
解释第三大的数是 1 。示例 2
输入[1, 2]
输出2
解释第三大的数不存在, 所以返回最大的数 2 。示例 3
输入[2, 2, 3, 1]
输出1
解释注意要求返回第三大的数是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数它们都排第二。在所有不同数字中排第三大的数为 1 。提示
1 nums.length 10^4-2^31 nums[i] 2^31 - 1
进阶 你能设计一个时间复杂度 O(n) 的解决方案吗 解法 遍历
思路先去重复再排序的做法/用堆的方法都是 n log n n\log n nlogn 级别的因此不考虑。下面是我第一次做的方法。先循环找出第一大(最大)的数再找出第二大的数再循环找出第三大的数 O ( 3 n ) O(3n) O(3n) 的复杂度。
class Solution {
public:int thirdMax(vectorint nums) {long firMax LONG_MIN, secMax LONG_MIN, thiMax LONG_MIN;for (int i 0; i nums.size(); i) if (nums[i] firMax) firMax nums[i]; for (int i 0; i nums.size(); i) if (nums[i] secMax nums[i] firMax) secMax nums[i];for (int i 0; i nums.size(); i) if (nums[i] thiMax nums[i] secMax) thiMax nums[i]; if (thiMax LONG_MIN) return firMax;return thiMax;}
};然后其实可以合成一个循环。像是冒泡或者是单调队列用 a , b , c a, b,c a,b,c 分别表示最大值次大值和第三大的数。
如果当前元素比 a a a 大则说明其一定比 b b b 和 c c c 都大。 我们同时更新 b b b 和 c c c 的值。 具体来说就是将 b b b 更新到 c c c a a a 更新到 b b b 可以形象地考虑成是把元素往后挤出去。否则我们继续判断是否比 b b b 大如果比 b b b 大那么肯定也比 c c c 大我们同时需要更新 c c c 的值。如果都不比 a a a 和 b b b 大我们继续判断是否比 c c c 大如果是我们更新c的值。
我们初始化 a , b , c a,b,c a,b,c 为 负无穷LONG_MIN。 这样我们最后只要判断 c c c 是不是负无穷即可如果是负无穷我们返回 a a a 否则我们返回 c c c 。
class Solution {
public:int thirdMax(vectorint nums) { long a LONG_MIN, b LONG_MIN, c LONG_MIN; for (int num : nums) {if (num a) {c b; b a; a num;} else if (num b num a) {c b; b num;} else if (num c num b) {c num;}}return (c LONG_MIN) ? a : c;}
};另一种不依赖元素范围的做法是将 a a a 、 b b b 和 c c c 初始化为空指针或空对象视作「无穷小」并在比较大小前先判断是否为空指针或空对象。遍历结束后若 c c c 为空则说明第三大的数不存在返回 a a a 否则返回 c c c 。
class Solution {
public:int thirdMax(vectorint nums) {int *a nullptr, *b nullptr, *c nullptr;for (int num : nums) {if (a nullptr || num *a) {c b;b a;a num;} else if (*a num (b nullptr || num *b)) {c b;b num;} else if (b ! nullptr *b num (c nullptr || num *c)) {c num;}}return c nullptr ? *a : *c;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 其中 n n n 是数组 nums \textit{nums} nums 的长度。空间复杂度 O ( 1 ) O(1) O(1) 。
