分治算法求解众数问题 - 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++代码内容：以下是使用分治算法解决众数问题的C++代码：

#include <iostream>
#include <vector>
#include <algorithm>

// 分治算法求解众数
void findMode(std::vector<int>& nums, int left, int right, int& mode, int& count) {
    // 递归结束条件
    if (left >= right) {
        mode = nums[left];
        count = 1;
        return;
    }

    // 分治过程
    int mid = left + (right - left) / 2;
    int leftMode, leftCount, rightMode, rightCount;
    findMode(nums, left, mid, leftMode, leftCount);
    findMode(nums, mid + 1, right, rightMode, rightCount);

    // 合并结果
    if (leftMode == rightMode) {
        mode = leftMode;
        count = leftCount + rightCount;
    } else {
        int leftModeCount = std::count(nums.begin() + left, nums.begin() + right + 1, leftMode);
        int rightModeCount = std::count(nums.begin() + left, nums.begin() + right + 1, rightMode);
        if (leftModeCount > rightModeCount) {
            mode = leftMode;
            count = leftModeCount;
        } else {
            mode = rightMode;
            count = rightModeCount;
        }
    }
}

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

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

    std::sort(nums.begin(), nums.end());

    int mode, count;
    findMode(nums, 0, n - 1, mode, count);

    std::cout << mode << std::endl;
    std::cout << count << std::endl;

    return 0;
}

算法思路

该算法的思路是使用分治法将问题分解为更小的子问题，然后将子问题的结果合并得到最终结果。具体来说，我们将多重集合S分为两半，分别求得左半部分和右半部分的众数及其重数。然后根据左右两个众数的重数进行比较，选择重数较大的众数作为当前区间的众数。最后递归地合并左右的结果，直到得到最终的众数及其重数。