第三大的数

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

class Solution { public: int thirdMax(vector<int>& nums) { } };

1.排序

class Solution { public: int thirdMax(vector<int>& nums) { sort(nums.begin(), nums.end(), greater<int>()); //默认sort从小到大，现在从大到小排序 for (int i = 1, diff = 1; i < nums.size(); ++i) { if (nums[i] != nums[i - 1] && ++diff == 3) { //前后数字不同，diff加加看数到第几个，这里不可以diff++ return nums[i]; } } return nums[0];//只有一个的才会输出这个 } };

2.有序集合

set有序去重，默认从小到大，没有push那些，插入会变有序所以没有前插后插，只有insert，erase。。

class Solution { public: //遍历数组，同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 3，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 3，且遍历结束后，若有序集合的大小为 3，其最小值就是数组中第三大的数；若有序集合的大小不足 3，那么就返回有序集合中的最大值。 int thirdMax(vector<int>& nums) { set<int> s; for (int num : nums) { s.insert(num); if (s.size() > 3) { s.erase(s.begin()); } } return s.size() == 3 ? *s.begin() : *s.rbegin(); };

遍历数组，同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 3，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 3，且遍历结束后，若有序集合的大小为 3，其最小值就是数组中第三大的数；若有序集合的大小不足 3，那么就返回有序集合中的最大值。

class Solution { public: int thirdMax(vector<int>& nums) { // set 会自动去重 + 升序排序 set<int> s; for (int num : nums) { s.insert(num); // 正确插入元素 } // 迭代器指向 set 起始位置 auto it = s.begin(); // 元素个数 >=3：返回第 3 大的数（set升序，倒数第3个） if (s.size() >= 3) { // 移动到倒数第 3 个元素 for (int i = 0; i < s.size() - 3; ++i) { it++; } } // 元素不足 3 个：返回最大值（最后一个元素） else { it = prev(s.end()); } return *it; // 返回迭代器指向的值 } };

3.一次遍历

遍历数组，并用三个变量 a、b 和 c 来维护数组中的最大值、次大值和第三大值，以模拟方法二中的插入和删除操作。为方便编程实现，我们将其均初始化为小于数组最小值的元素，视作「无穷小」，比如 −2 63 等。

class Solution { public: int thirdMax(vector<int> &nums) { long a = LONG_MIN, b = LONG_MIN, c = LONG_MIN; for (long num : nums) { if (num > a) { c = b; b = a; a = num; } else if (a > num && num > b) { c = b; b = num; } else if (b > num && num > c) { c = num; } } return c == LONG_MIN ? a : c; } };