Given an array of size n, find the majority element. The majority element is the element that appears more than
⌊ n/2 ⌋times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example：
Input: [3,2,3]
Output: 3
Input: [2,2,1,1,1,2,2]
Output: 2
解释下题目：
简单说就是找出现最多的那个数字
1. divide and conquer
实际耗时：4ms
public int majorityElement(int[] nums) {
return getMajorityNumber(nums, 0, nums.length - 1);
}
private int getMajorityNumber(int[] nums, int start, int end) {
int mid = 0;
if (start == end) {
return nums[start];
} else {
mid = (end - start) >> 1;
int left = getMajorityNumber(nums, start, start + mid);
int right = getMajorityNumber(nums, start + mid + 1, end);
if (left == right) {
return left;
} else {
int leftCount = count(nums, start, start + mid, left);
int rightCount = count(nums, start + mid, end, right);
return leftCount > rightCount ? left : right;
}
}
}
private int count(int[] nums, int start, int end, int num) {
int count = 0;
for (int i = start; i < end; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
思路，如果一个数字想要全局出现最多，那么它一定是在所有的出现最多的候选者中产生。利用这个思路去递归查找即可。举个例子，如果数字a是全局出现次数最多的，那么在数组的左半部分出现的最多的和数组右半部分出现最多的两个数字中，至少有一个数字是它。
