用c++写分治法求众数

以下是用C++实现分治法求众数的代码：

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& nums) {
    if (nums.empty()) {
        return -1;
    }
    if (nums.size() == 1) {
        return nums[0];
    }
    vector<int> left(nums.begin(), nums.begin() + nums.size() / 2);
    vector<int> right(nums.begin() + nums.size() / 2, nums.end());
    int left_majority = majorityElement(left);
    int right_majority = majorityElement(right);
    if (left_majority == right_majority) {
        return left_majority;
    }
    int left_count = 0, right_count = 0;
    for (int num : nums) {
        if (num == left_majority) {
            left_count++;
        } else if (num == right_majority) {
            right_count++;
        }
    }
    if (left_count > right_count) {
        return left_majority;
    } else {
        return right_majority;
    }
}

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

该算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)。