題目
給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素闸与。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。
你可以假設(shè)數(shù)組是非空的蔚龙，并且給定的數(shù)組總是存在多數(shù)元素映胁。
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:輸入: [2,2,1,1,1,2,2]
輸出: 2來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/majority-element
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)坑填，非商業(yè)轉(zhuǎn)載請注明出處。
解法1：
class Solution {
public int majorityElement(int[] nums) {
return major(nums,0,nums.length-1);
}
public int major(int[] nums, int start, int end){
if(start==end){
return nums[start];
}
int mid=(start+end)/2;
int left=major(nums,start,mid);
int right=major(nums,mid+1,end);
return element(nums,left,right,start,mid,end);
}
public int element(int[] nums, int left, int right,int start, int mid,int end){
int leftcount=0;
for(int i = start ; i <=mid; i++){
if(nums[i]==left){
leftcount++;
}
}
int rightcount=0;
for(int i = mid+1 ; i <=end; i++){
if(nums[i]==right){
rightcount++;
}
}
return leftcount>rightcount ? left:right;
}
}
