刷爆力扣之第三大的数

刷爆力扣之第三大的数

HELLO，各位看官大大好，我是阿呆 🙈🙈🙈
今天阿呆继续记录下力扣刷题过程，收录在专栏算法中 😜😜😜

该专栏按照不同类别标签进行刷题，每个标签又分为 Easy、Medium、Hard 三个等级 👊👊👊

本部分所有题目均来自于LeetCode 网，并于每道题目下标明具体力扣网原题链接 🏃🏃🏃

OK，兄弟们，废话不多直接上题，冲冲冲 🌞🌞🌞

一 🏠 题目描述

414. 第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。
1
2
3

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。
1
2
3

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
1
2
3
4

提示：

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？

二 🏠破题思路

2.1 🚀 关键信息

解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎

题干很容易理解，就是返回此数组中 第三大的数 🌸🌸🌸

提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃

2.2 🚀 思路整理

分类讨论法

定义数组的前三大的值，遍历数组会遇到以下三种情况

① 当前值比最大值大，则改变前大三的值

② 当前值比最大值小，比中间值大，则改变第二大和第三大两个值

③ 当前值比最小值大，则仅改变第三的值

返回时判断第三大值是否为 LONG_MIN ，若为则返回第一大值，否则返回第三大值 🌺🌺🌺

整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃

三 🏠 代码详解

3.1 🚀 代码实现

按照我们刚才的破题思路，直接代码走起来 👇👇👇👇

int thirdMax(std::vector 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];
            } else if (nums[index] < firstNum && nums[index] > secondNum) { //比中间值大，则改变两个值
                thirdNum = secondNum;
                secondNum = nums[index];
            } else if (nums[index] > thirdNum && nums[index] < secondNum){ //比最小值大，则改变一个值
                thirdNum = nums[index];
            }
        }
    
        return  thirdNum == LONG_MIN ? firstNum : thirdNum;  //判断结果是否存在第三大的值
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.2 🚀 细节解析

看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃

那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇

thirdNum == LONG_MIN ? firstNum : thirdNum //判断结果是否存在第三大的值
1

返回时判断第三大值是否为 LONG_MIN ，若为则返回第一大值，否则返回第三大值 🐳🐳🐳

四 🏠 心路历程

为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈

博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题

未考虑的点已在上述代码注释提到了，实现方式效率和简洁性太差 😭😭😭 ，代码如下 👇👇👇👇

int thirdMax(std::vector nums) {
    std::list threeElemArray = {nums[0]}; //把当前值当做最大值

    //遍历输入数组
    for (int index = 1; index < nums.size(); ++index) { // index 的范围是 [1,nums.size()) 数组下标是从 0 开始的
        std::list::iterator threeElemArrayIter = threeElemArray.begin(); //拿到迭代器
        if (nums[index] == *threeElemArrayIter || nums[index] == *threeElemArray.rbegin()) continue; //如果三元素组

        if (nums[index] > *threeElemArrayIter) {	//如果当前值大于三元素组最大值
            threeElemArray.push_front(nums[index]); //直接插入三元素组的头
        } else if (nums[index] < *threeElemArray.rbegin()) { //如果当前值小于三元素组最大值
            threeElemArray.insert(threeElemArray.end(), nums[index]);  //直接插入三元素组的尾
        } else {
            if (nums[index] == *(++threeElemArrayIter)) continue;

            //走到这个分支说明当前三元素值大小至少为 2
            if (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 是在头的位置, ++ 会内存越界
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

五 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

如果各位看官大大觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪