一 🏠 题目描述
414. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1：
输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。
示例 2：
输入：[1, 2] 输出：2 解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：
输入：[2, 2, 3, 1] 输出：1 解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
提示：
1 <= nums.length <=104-231 <= nums[i] <=231-1
进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
题干很容易理解，就是返回此数组中 第三大的数 🌸🌸🌸
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
分类讨论法
定义数组的前三大的值，遍历数组会遇到以下三种情况
① 当前值比最大值大，则改变前大三的值
② 当前值比最大值小，比中间值大，则改变第二大和第三大两个值
③ 当前值比最小值大，则仅改变第三的值
返回时判断第三大值是否为 LONG_MIN ，若为则返回第一大值，否则返回第三大值 🌺🌺🌺
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
int thirdMax(std::vector<int> nums) { //使用三个元素,且值为 LONG_MIN (一定比输入的 int 小) //极值替代这点没有想到, 使用三个元素这点也没有想到 long firstNum = LONG_MIN, secondNum = LONG_MIN, thirdNum = LONG_MIN; //因为输入的一定比极值小,所以只有三个条件满足则走各个分支即可 for (int index =0; index < nums.size(); ++index){ if (nums[index] > firstNum){ //比最大值大，则改变三个值 thirdNum = secondNum; secondNum = firstNum; firstNum = nums[index]; } elseif (nums[index] < firstNum && nums[index] > secondNum) { //比中间值大，则改变两个值 thirdNum = secondNum; secondNum = nums[index]; } elseif (nums[index] > thirdNum && nums[index] < secondNum){ //比最小值大，则改变一个值 thirdNum = nums[index]; } } return thirdNum == LONG_MIN ? firstNum : thirdNum; //判断结果是否存在第三大的值 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
thirdNum == LONG_MIN ? firstNum : thirdNum //判断结果是否存在第三大的值
返回时判断第三大值是否为 LONG_MIN ，若为则返回第一大值，否则返回第三大值 🐳🐳🐳
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题
未考虑的点已在上述代码注释提到了，实现方式效率和简洁性太差 😭😭😭 ，代码如下 👇👇👇👇
int thirdMax(std::vector<int> nums) { std::list<int> threeElemArray = {nums[0]}; //把当前值当做最大值 //遍历输入数组 for (int index =1; index < nums.size(); ++index) { // index 的范围是 [1,nums.size()) 数组下标是从 0 开始的 std::list<int>::iterator threeElemArrayIter = threeElemArray.begin(); //拿到迭代器 if (nums[index] == *threeElemArrayIter || nums[index] == *threeElemArray.rbegin()) continue; //如果三元素组 if (nums[index] > *threeElemArrayIter) { //如果当前值大于三元素组最大值 threeElemArray.push_front(nums[index]); //直接插入三元素组的头 } elseif (nums[index] < *threeElemArray.rbegin()) { //如果当前值小于三元素组最大值 threeElemArray.insert(threeElemArray.end(), nums[index]); //直接插入三元素组的尾 } else { if (nums[index] == *(++threeElemArrayIter)) continue; //走到这个分支说明当前三元素值大小至少为 2if (nums[index] > *threeElemArrayIter) { //大于第二 threeElemArray.insert(threeElemArrayIter, nums[index]); //插在第二前面 } else { //小于第二,考虑是否大于第三,走到这个分支说明大于第三 threeElemArray.insert(++threeElemArrayIter, nums[index]); //插在第二后面 } } if (threeElemArray.size() > 3) threeElemArray.pop_back(); //删除最后元素 } //如果第三大数不存在，则返回数组中最大的数 return threeElemArray.size() !=3 ? *(threeElemArray.begin()) : *(threeElemArray.rbegin()); //rend 是在头的位置, ++ 会内存越界 }
