LeetCode第 414 题：第三大的数(C++)

414. 第三大的数 - 力扣（LeetCode） 典型的topk，优先级队列，不过这儿需要处理重复元素，可以使用哈希表自动去重

class Solution { public: int thirdMax(vector<int>& nums) { unordered_set<int> s(nums.begin(), nums.end()); int n = s.size(); if(n < 3) return *max_element(s.begin(), s.end()); priority_queue<int, vector<int>, greater<int>> q;//小顶堆 auto it = s.begin(); for(int i = 0; i < 3; ++i){ q.push(*it); ++it; } while(it != s.end()){ if(*it > q.top()){ q.pop(); q.push(*it); } ++it; } return q.top(); } };

其实直接使用set自动排序就可以了。

也可以使用三个变量维护：

class Solution { public: int thirdMax(vector<int>& nums) { long m1 = -3e9, m2 = -3e9, m3 = -3e9;//m1 > m2 > m3 for (const auto &x : nums) { if (x == m1 || x == m2 || x == m3) continue; if (x > m1) { m3 = m2; m2 = m1; m1 = x; } else if (x > m2) { m3 = m2; m2 = x; } else if (x > m3) m3 = x; } if (m3 == -3e9) return m1; else return m3; } };