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;

    }

}

巴特西

Leetcode之分治法专题-169. 求众数（Majority Element）

最新文章

热门文章