题意: 给出一个数组, 求第三大的数字是多少, 重复的数字并不算在内, 比如 [1, 2, 2, 3] 第3大的数字是1 而不是 2.
Using std::set
set 是集合, 是有序的(从小到大), 集合中不包含重复的元素, 所以我们可以遍历数组并把数字添加到集合中. 在这过程中, 如果集合大小大于三个, 就把最小的元素删除. 我们不能直接按照索引的访问集合中的元素, 但是我们可以用迭代器 rbegin() 和 begin() 来访问集合中最大和最小的元素.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution { public: int thirdMax(vector<int>& nums) { set<int> data; for (const auto &n: nums) { data.insert(n); if (data.size() > 3) { data.erase(data.begin()); // 去掉最小的 } } return data.size() < 3 ? *data.rbegin() : *data.begin(); } }; |
class Solution { public: int thirdMax(vector<int>& nums) { set<int> data; for (const auto &n: nums) { data.insert(n); if (data.size() > 3) { data.erase(data.begin()); // 去掉最小的 } } return data.size() < 3 ? *data.rbegin() : *data.begin(); } };
Using std::priority_queue
默认, 优先队列每次取出的元素都是队列中最大的, 我们可以用 std::greater 来取反. 创建优先队列的复杂度是 O(nlogn), 但是由于我们保持最大长度为3, 所以实际上复杂度是 O(logn). 我们还需要借住 unordered_set 无序集合来保持优先队列中的元素是唯一的.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: int thirdMax(vector<int>& nums) { unordered_set<int> cache; priority_queue<int, vector<int>, std::greater<int>> data; // 从小到大出列顺序 for (const auto &n: nums) { if (cache.count(n)) { // 已经出现过了 continue; } cache.insert(n); // 标记 data.push(n); // 入列 if (data.size() > 3) { data.pop(); // 去掉最小的 } } if (data.size() < 3) { while (data.size() > 1) { data.pop(); // 去掉最小的 } return data.top(); //剩下就是最大的 } return data.top(); //第三大 } }; |
class Solution { public: int thirdMax(vector<int>& nums) { unordered_set<int> cache; priority_queue<int, vector<int>, std::greater<int>> data; // 从小到大出列顺序 for (const auto &n: nums) { if (cache.count(n)) { // 已经出现过了 continue; } cache.insert(n); // 标记 data.push(n); // 入列 if (data.size() > 3) { data.pop(); // 去掉最小的 } } if (data.size() < 3) { while (data.size() > 1) { data.pop(); // 去掉最小的 } return data.top(); //剩下就是最大的 } return data.top(); //第三大 } };
using std::vector
我们还可以用 vector来存储任意时刻的最大三个数. 循环内部有 查找和排序 , 但由于数组大小都是3, 所以整体的复杂度是 O(n).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: int thirdMax(vector<int>& nums) { vector<int> max3; for (const auto &n: nums) { if (std::find(max3.begin(), max3.end(), n) != max3.end()) { // 如果有重复就跳过 continue; } max3.push_back(n); sort(max3.begin(), max3.end()); //排序3个数 if (max3.size() > 3) { max3.erase(max3.begin()); // 删掉最小的那个数 } } if (max3.size() == 3) { return max3[0]; } else { return max3[max3.size() - 1]; } } }; |
class Solution { public: int thirdMax(vector<int>& nums) { vector<int> max3; for (const auto &n: nums) { if (std::find(max3.begin(), max3.end(), n) != max3.end()) { // 如果有重复就跳过 continue; } max3.push_back(n); sort(max3.begin(), max3.end()); //排序3个数 if (max3.size() > 3) { max3.erase(max3.begin()); // 删掉最小的那个数 } } if (max3.size() == 3) { return max3[0]; } else { return max3[max3.size() - 1]; } } };
英文: C++ Coding Exercise – Find Third Maximum in O(n)
GD Star Rating
loading...
本文一共 349 个汉字, 你数一下对不对.loading...
上一篇: 试用 Linkedin (领英) 高级帐号 (Premium)
下一篇: 编程练习题: 找出N叉树的深度
扫描二维码,分享本文到微信朋友圈