C++ 算法：查找多重集合的众数

问题描述

给定含有 n 个元素的多重集合 S，每个元素在 S 中出现的次数称为该元素的重数。多重集合 S 中重数最大的元素称为众数。例如，S={1, 2, 2, 2, 3, 5}。多重集合 S 的众数是 2，其重数为 3。对于给定的由 n 个自然数组成的多重集合 S，计算 S 的众数及其重数。如果出现多个众数，请输出最小的那个。

输入

输入数据的第 1 行是多重集合 S 中元素个数 n（n<1300000）；接下来的 n 行中，每行有一个最多含有 5 位数字的自然数，。

输出

输出数据的第 1 行给出众数，第 2 行是重数。

样例

Input 6 1 2 2 2 3 5

Output 2 3

C++ 代码实现

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

pair<int, int> findMode(vector<int>& nums) {
    unordered_map<int, int> count;
    int mode = 0;
    int maxCount = 0;

    for (int num : nums) {
        count[num]++;
        if (count[num] > maxCount) {
            maxCount = count[num];
            mode = num;
        }
    }

    return make_pair(mode, maxCount);
}

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    pair<int, int> mode = findMode(nums);
    cout << mode.first << endl;
    cout << mode.second << endl;

    return 0;
}

算法解释

使用 unordered_map 存储每个数字出现的次数。
遍历输入的数字列表，更新 unordered_map 中对应数字的计数。
在遍历过程中，维护当前众数 mode 和其出现次数 maxCount。
当遇到出现次数大于 maxCount 的数字时，更新 mode 和 maxCount。
返回 mode 和 maxCount 作为最终结果。

代码解析

findMode 函数接受一个 vector<int> 类型的数字列表作为参数，返回一个 pair<int, int> 类型的结果，其中第一个元素是众数，第二个元素是众数出现的次数。
main 函数首先读取输入的数字个数 n，然后读取 n 个数字并存储在 vector<int> 类型的 nums 中。
调用 findMode 函数计算众数和重数，并将结果存储在 pair<int, int> 类型的 mode 中。
最后，输出 mode 的第一个元素 (众数) 和第二个元素 (重数)。

总结

本文详细讲解了如何使用 C++ 语言解决查找多重集合的众数问题，并提供了详细的算法解释和代码实现。希望本文能够帮助读者更好地理解和学习相关算法和代码。