算法学习：每日一题 No.414

414. 第三大的数

假设这道题的要求是返回数组中第 $K$ 大的数。

背景：数组

目的：找到第 $K$ 大的数

方法：有序集合

在C++中存在 有序集合 和 无序集合 两种集合，分别对应下方的头文件：

#include <set>
#include <unordered_set>
set<T> s;
unordered_set<T> us;

通常，使用无序集合要比有序集合要好些，可以避免不必要的排序，但是这道题要我们找到第几大的数字，这可能需要排序。

我们将该集合的元素个数限定在 $K$ 个以内，这样这K个元素已经排好序的状态，第K大的数字就在集合的第一位（因为是有序集合）。

按照题意，我们还需要考虑集合中的元素小于 K 时，需要返回当前元素中的最大值。在这个有序集合中，最大值在集合的末尾。

如何获得集合起始和末尾的元素呢？

在 set 中存在 begin() 和 rbegin() 两个方法。begin() 返回的是一个首部的迭代器，实际上是一个指针，通过解引用我们就可以获得第一个元素。rbegin() 返回的是右端开始的首部迭代器，也是一个指针，解引用就可以获得末尾的元素。

set 中还有这样几个方法

end() 指向的是末尾元素的后一个元素，通常为 nullptr

rend() 和 end() 的遍历方向向反，所以其指向的是遍历元素末尾的后一个元素

可以猜测这个迭代器的实现是一个双向链表

来看一看代码：

#include <set>
using namespace std;

class Solution {
public:
    int thirdMax(vector<int>& nums, int k = 3) {
        set<int> s;
        for (auto & num : nums)
        {
            s.insert(num);
            if (s.size() > k)
            {
                s.erase(s.begin());
            }
        }
        return s.size() == 3 ? *s.begin() : *s.rbegin();
    }
};