C++ 编程练习题 – 找出第三大的数

JustYY.com 小赖子的英国生活和资讯

7 years ago

题意: 给出一个数组, 求第三大的数字是多少, 重复的数字并不算在内, 比如 [1, 2, 2, 3] 第3大的数字是1 而不是 2.

Using std::set

set 是集合, 是有序的(从小到大), 集合中不包含重复的元素, 所以我们可以遍历数组并把数字添加到集合中. 在这过程中, 如果集合大小大于三个, 就把最小的元素删除. 我们不能直接按照索引的访问集合中的元素, 但是我们可以用迭代器 rbegin() 和 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();
    }
};

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 无序集合来保持优先队列中的元素是唯一的.

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).

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)

C/C++编程

强烈推荐

英国代购-畅购英伦
TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
Quidco 返现 (也是很不错的英国返现网站, 返现率高)
注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
注册就送10美元, 免费使用2个月的阿里云主机(性价比超高, 每月只需4.5美元)
注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
刷了美国运通信用卡一年得到的积分换了 485英镑
注册就送50英镑 – 英国最便宜最划算的电气提供商
能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

Using std::set

Using std::priority_queue

using std::vector

C/C++编程

强烈推荐

相关文章：