众数问题（分治法）c++

众数问题是指在一个给定的数组中，找出出现次数最多的元素。分治法是一种解决众数问题的常用方法。下面是使用分治法解决众数问题的C++代码示例：

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

using namespace std;

int findMajorityElement(vector<int>& nums, int left, int right) {
    // 如果只有一个元素，则它就是众数
    if (left == right) {
        return nums[left];
    }

    // 分别找出左半部分和右半部分的众数
    int mid = left + (right - left) / 2;
    int leftMajority = findMajorityElement(nums, left, mid);
    int rightMajority = findMajorityElement(nums, mid + 1, right);

    // 如果左右两部分的众数相同，则直接返回
    if (leftMajority == rightMajority) {
        return leftMajority;
    }

    // 统计左右两部分的众数出现次数
    int leftCount = 0, rightCount = 0;
    for (int i = left; i <= right; i++) {
        if (nums[i] == leftMajority) {
            leftCount++;
        } else if (nums[i] == rightMajority) {
            rightCount++;
        }
    }

    // 返回出现次数较多的众数
    return leftCount > rightCount ? leftMajority : rightMajority;
}

int majorityElement(vector<int>& nums) {
    return findMajorityElement(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums = {1, 2, 2, 2, 3};
    int majority = majorityElement(nums);
    cout << "The majority element is: " << majority << endl;
    return 0;
}

上述代码中，`findMajorityElement`函数使用递归的方式将数组分为左右两部分，并分别找出左右两部分的众数。然后统计左右两部分的众数出现次数，最后返回出现次数较多的众数。`majorityElement`函数是对`findMajorityElement`函数的调用，用于处理整个数组。