Leetcode之分治法专题-169. 求众数（Majority Element）
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
分治法，顾名思义，分而治之，就是把要求解的问题，一分为二，在每个分支上再求解。 这题里，我们可以求出一个mid=(L+R)>>>1;
求mid的左边和右边的众数，最后可以求得整个数组的众数。
如果只有一个数的时候，即L==R时，返回这个数，因为一个数的众数就是他自己。
如果左右分支的众数一样的话，随意返回一个就行。
如果左右分支的众数不一样，那么计算左右分支中他们各自众数的数量，返回数量大的，最后就是整个数组的众数了。
class Solution {
public int majorityElement(int[] nums) {
return fun(nums,0,nums.length-1);
}
private int fun(int[] nums, int L, int R) {
if(L==R){
return nums[L];
}
int mid = (L+R)>>>1;
int left = fun(nums,L,mid);
int right = fun(nums,mid+1,R);
if(left==right){
return left;
}
int leftCount = 0;
int rightCount = 0;
for (int i = L; i <mid ; i++) {
if(nums[i]==left) leftCount++;
}
for (int i = mid; i <R ; i++) {
if(nums[i]==right) rightCount++;
}
return leftCount>rightCount?left:right;
}
}