【问题描述】

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.

【问题分析】

return count(nums.begin()+left,nums.begin()+right+1,LeftNum)>count(nums.begin()+left,nums.begin()+right+1,RightNum)?LeftNum:RightNum;利用递归找出子数组出现最多的数。
【源代码】
1、map方法：
class Solution {public:    int majorityElement(vector<int>& nums) {        map<int,int> hash;        for (int i = 0; i < nums.size(); i++) {        	if (++hash[nums[i]] > nums.size() / 2) {        		return nums[i];        	}        }    }};2、分而治之方法
class Solution {public:    int majorityElement(vector<int>& nums) {        return majority(nums,0,nums.size()-1);    }PRivate:    int majority(vector<int>& nums,int left,int right) {    	if (left==right) {    		return nums[left];    	}    	int mid=left+((right-left)>>1);    	int LeftNum=majority(nums,left,mid);    	int RightNum=majority(nums,mid+1,right);    	if (LeftNum==RightNum)	return LeftNum;    	return count(nums.begin()+left,nums.begin()+right+1,LeftNum)>count(nums.begin()+left,nums.begin()+right+1,RightNum)?LeftNum:RightNum;   }};