题目
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:输入: [2,2,1,1,1,2,2]
输出: 2来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法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;
}
}
网友评论