leetcode 414. Third Maximum Number 第三大数据 + set + 最大堆

港控/mmm° 2022-06-03 20:10 140阅读 0赞

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.

本提题意就是寻找第三大的数据，这里我们使用一个set来表示，注意set是一个高度平衡的二叉搜索树，所以注意**set数据结构的使用**

[set–常见成员函数及基本用法][set]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <bitset>
    
    using namespace std;
    
    class Solution
    {
    public:
        int thirdMax(vector<int>& nums)
        {
            set<int> ss;
            for (int i : nums)
            {
                ss.insert(i);
                if (ss.size() > 3)
                    ss.erase(ss.begin());
            }
            if(ss.size()==3)
                return *(ss.begin());
            else
                return *(ss.rbegin());
        }
    };

[set]: https://www.cnblogs.com/zyxStar/p/4542835.html

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode题目#414（数组类）——第三大的数

原题链接及题目如下： https://leetcode-cn.com/problems/third-maximum-number/submissions/ ![在这里插

╰半橙微兮°/ 2023年01月08日 04:27/ 0 赞/ 219 阅读

相关（力扣）第414. 第三大的数

414. 第三大的数 -------------------- 题目要求：给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。 -

蔚落/ 2022年11月12日 09:33/ 0 赞/ 157 阅读

相关（js）leetcode 414. 第三大的数

题目： > 给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。 > > 示例 1： > > 输入：\[3, 2, 1\] > 输出：

红太狼/ 2022年10月29日 11:29/ 0 赞/ 159 阅读

相关【Leetcode】414. Third Maximum Number

思路：将数组升序排列。 j记录当前找到的是第几大数。从最后一个元素开始往前处理，一旦j==3，立即返回当前元素，若当前元素与前一个元素不等，则j++。遍历完毕后，

清疚/ 2022年10月01日 02:48/ 0 赞/ 134 阅读

相关 LeetCode--414. 第三大的数(C++描述)

// Source : https://leetcode-cn.com/problems/third-maximum-number/submissions/ // Date

刺骨的言语ヽ痛彻心扉/ 2022年08月28日 09:44/ 0 赞/ 149 阅读

相关 Leetcode 414. 第三大的数

Leetcode 414. 第三大的数 package com.bingoabin.algorithm.hashmap; import java.u

待我称王封你为后i/ 2022年08月28日 08:50/ 0 赞/ 179 阅读

相关 414. Third Maximum Number

/ Given a non-empty array of integers, return the third maximum number in t

- 日理万妓/ 2022年06月08日 00:51/ 0 赞/ 138 阅读

相关 leetcode 414. Third Maximum Number 第三大数据 + set + 最大堆

Given a non-empty array of integers, return the third maximum number in this array. If i

港控/mmm°/ 2022年06月03日 20:10/ 0 赞/ 141 阅读

相关 LeetCode414. 第三大的数

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。示例 1: 输入: [3, 2, 1]

雨点打透心脏的1/2处/ 2022年05月23日 07:35/ 0 赞/ 202 阅读

相关【LeetCode】414. 第三大的数

题目链接：[https://leetcode-cn.com/problems/third-maximum-number/description/][https_leetcode

男娘i/ 2022年05月08日 06:54/ 0 赞/ 210 阅读