数组中有一个数字出现的次数超过数组长度的一半，请用分治法找出这个数字并用Java实现

思路：

分治法的思想是将问题分解成较小的子问题，然后递归解决。对于这个问题，我们可以将数组分成两个子数组，分别求出两个子数组中出现次数超过一半的数字，然后比较两个数字的出现次数，得出整个数组中出现次数超过一半的数字。

具体实现：

1.编写一个函数findMajority，它接收一个整型数组和左右边界left、right作为参数，返回数组中出现次数超过一半的数字。

2.递归调用函数findMajority，将数组分成两个子数组，分别求出出现次数超过一半的数字majority1和majority2。

3.比较两个数字的出现次数，取出现次数较多的数字作为整个数组中出现次数超过一半的数字。

4.统计一个数字在数组中出现的次数，可以用一个循环遍历整个数组，或者用HashMap来存储数字和出现次数的映射关系。

代码实现如下：

import java.util.HashMap;

public class MajorityElement {
    public int findMajority(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        int majority1 = findMajority(nums, left, mid);
        int majority2 = findMajority(nums, mid + 1, right);
        if (majority1 == majority2) {
            return majority1;
        }
        int count1 = count(nums, majority1, left, right);
        int count2 = count(nums, majority2, left, right);
        return count1 > count2 ? majority1 : majority2;
    }

    public int count(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;
    }

    public static void main(String[] args) {
        MajorityElement solution = new MajorityElement();
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        int majority = solution.findMajority(nums, 0, nums.length - 1);
        System.out.println("The majority element is " + majority);
    }
}

时间复杂度：O(nlogn)

空间复杂度：O(1)