美文网首页
分治算法w2-T17 169. 多数元素-简单

分治算法w2-T17 169. 多数元素-简单

作者: 小院闲窗春已深 | 来源:发表于2020-05-08 20:38 被阅读0次

    题目

    给定一个大小为 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;
        }
    }
    
    
    

    相关文章

      网友评论

          本文标题:分治算法w2-T17 169. 多数元素-简单

          本文链接:https://www.haomeiwen.com/subject/dbmqnhtx.html