众数问题求解（分治法）Java代码

以下是使用分治法求众数（出现次数超过数组长度一半的数）的Java代码：

public class MajorityElement {
    public int majorityElement(int[] nums) {
        return majorityElement(nums, 0, nums.length - 1);
    }
    
    private int majorityElement(int[] nums, int left, int right) {
        // base case
        if (left == right) {
            return nums[left];
        }
        
        // divide
        int mid = left + (right - left) / 2;
        int leftMajority = majorityElement(nums, left, mid);
        int rightMajority = majorityElement(nums, mid + 1, right);
        
        // conquer
        if (leftMajority == rightMajority) {
            return leftMajority;
        }
        
        int leftCount = countInRange(nums, leftMajority, left, right);
        int rightCount = countInRange(nums, rightMajority, left, right);
        
        return leftCount > rightCount ? leftMajority : rightMajority;
    }
    
    private int countInRange(int[] nums, int num, int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }
}

该代码使用了递归的分治方法，将原问题划分为两个子问题，并在子问题中递归求解。在递归到最小子问题时，直接返回该子问题的结果。在逐层回溯时，合并子问题的结果，进而得到原问题的结果。

该代码的时间复杂度为 O(nlogn)，其中 n 为数组的长度。该算法的空间复杂度为 O(logn)，因为递归栈的深度为 O(logn)。