0414. Third Maximum Number ========================== 题目信息 -------- :题号: 0414 :难度: Easy :主题: 不同数值、第三大、重复元素、最大值回退 :原题: `LeetCode 0414 `_ :重点: 排名按不同数值计算、重复值只占一个名次、不同值不足三个时返回最大值 题目重述 -------- 给定整数数组 ``nums``,返回数组中第三大的不同数值。重复出现的相同整数只算一个名次;若数组中不同数值少于三个,则返回其中的最大值。 ``nums.length`` 位于 ``[1, 10^4]``,每个元素都在 32 位有符号整数范围内。``-2^31`` 等边界值与其他整数一样是合法候选,不能把某个整数值用作“尚未设置”的特殊标记。 自建示例 -------- 重复最大值不重复占名次: .. code-block:: text 输入:nums = [9, 2, 9, 7, 5] 输出:5 解释:不同数值按降序为 9、7、5、2,因此第三大不同值是 5。 不同值不足三个: .. code-block:: text 输入:nums = [4, 4] 输出:4 解释:数组只有一个不同数值,按题目要求返回最大值 4。 只保留最大的三个不同值 ------------------------ 用有序集合维护当前见过的最大三个不同数值。插入重复值不会改变集合;插入新值后若集合超过三个,就删除最小值。扫描结束时,集合大小为 3 则最小者是第三大,否则最大者是题目要求的回退答案。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int thirdMax(std::vector& nums) { std::set top; for (int value : nums) { top.insert(value); if (top.size() > 3) top.erase(top.begin()); } if (top.size() == 3) return *top.begin(); return *top.rbegin(); } }; 代码分析 -------- 集合既去除重复名次,又把维护规模限制为 3,不需要使用可能与合法输入冲突的哨兵值;``-2^31`` 也能正常存储。每次操作是固定大小集合上的 ``O(log 3)``,总体时间可视为 ``O(n)``,额外空间为 ``O(1)``。