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

港控/mmm° 2022-06-03 20:10 115阅读 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 条评论，115人围观）

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

相关阅读

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

414. 第三大的数给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。 C++ // // Created by

港控/mmm°/ 2024年03月31日 16:50/ 0 赞/ 52 阅读

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

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

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

相关【Leetcode】414. Third Maximum Number

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

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

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

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

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

相关 Leetcode 414. 第三大的数

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

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

相关 [leetcode]: 414. Third Maximum Number

1.题目 Given a non-empty array of integers, return the third maximum number in this arr

本是古典何须时尚/ 2022年06月14日 06:18/ 0 赞/ 127 阅读

相关 414. Third Maximum Number

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

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

相关 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 赞/ 116 阅读

相关 LeetCode414. 第三大的数

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

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

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

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

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