求解众数问题，给定一个整数序列，给定一个整数序列，每个元素出现的次数称为重数，重数最大的元素称为众数，编写一个实验程序对递增有序序列求众数。例如：a={1,2,2,2,3,3,5,6,6,6,6}，其众数为6，重数为4。 求解思路为：解:求众数的方法有多种,这里采用分治法求众数。 用全局变量num和maxcnt分别存放α的众数和重数(maxcnt的初始值为0)。对于至少含有一个元素的序列a[low..high],以中间位置mid为界限,求出a[mid]元素的重数cnt,即 a[left.. right]均为a[mid],cnt- right—left＋1,若cnt大于maxcnt,置num-a[midJ，maxcnt- cnt。然后对左序列a[low..left-1]和右序列a[right+1..high]递归求解众数，完整代码c++求

下面是采用分治法求解众数的完整代码实现（C++ 版本）：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int num = 0, maxcnt = 0;
        divide(nums, 0, nums.size() - 1, num, maxcnt);
        return num;
    }

private:
    void divide(vector<int>& nums, int left, int right, int& num, int& maxcnt) {
        if (left == right) {
            num = nums[left];
            maxcnt = 1;
            return;
        }
        int mid = left + (right - left) / 2;
        int left_num = 0, left_maxcnt = 0;
        divide(nums, left, mid, left_num, left_maxcnt);
        int right_num = 0, right_maxcnt = 0;
        divide(nums, mid + 1, right, right_num, right_maxcnt);
        int cnt = 0;
        if (left_num == right_num) {
            num = left_num;
            maxcnt = left_maxcnt + right_maxcnt;
            return;
        }
        for (int i = left; i <= right; i++) {
            if (nums[i] == left_num) {
                cnt++;
            } else if (nums[i] == right_num) {
                cnt--;
            }
        }
        if (cnt > 0) {
            num = left_num;
            maxcnt = left_maxcnt + cnt;
        } else {
            num = right_num;
            maxcnt = right_maxcnt - cnt;
        }
    }
};

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