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.
思路.1
排序，选择第n/2个数，调用STL的sort,所以时间复杂度是O(nlogn)
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nuns.end());
return nums[nums.size()/2];
}
};
思路2
设置一个计数，当count为0时设置majority的值，如果下一个值与majority相同则count+1,如果不同，则-1，当count==0时，对majority重新赋值，因为majority的个数肯定大于n/2所以最后>0的count的肯定是majority，这样，就只需要遍历一遍就可以求出majority，时间复杂度为O(n)
class Solution {
public:
int majorityElement(vector<int>& nums) {
int Majority = nums[0];
int count = 1;
for( int i = 1; i < nums.size(); i++ ){
if( count == 0 ){
count++;
Majority = nums[i];
}
else if( Majority == nums[i] ){
count++;
}
else if ( Majority != nums[i] ){
count--;
}
}
return Majority;
}
};