即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 169. Majority Element

编程语言 fight_girl 15℃ 0评论

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.


参考自
点击打开链接
 ,一篇很好的博客
public class Solution {
    public int majorityElement(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public int helper(int [] nums,int begin,int end){
        if(begin==end){
            return nums[begin];
        }else{
            int mid = begin+ (end-begin)/2;
            int left = helper(nums,begin,mid);
            int right = helper(nums,mid+1,end);
            if(left == right){
                return left;
            }else{
                int leftcount=0,rightcount=0;
                for(int i=begin;i<=end;i++){
                    if(nums[i]==left){
                        leftcount++;
                    }else if(nums[i]==right){
                        rightcount++;
                    }
                }
                if(leftcount >rightcount){
                    return left;
                }else{
                    return right;
                }
            }
        }
    }
}


转载请注明:CodingBlog » LeetCode 169. Majority Element

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情