1.题目
2.法一：用sort
先用sort排序后，因为定义的“多数元素”是在数组中出现次数大于n/2的元素，所以可以返回下标为n/2的数组元素即所求。
用sort的时间复杂度就是O(nlogn)而非O(n)了。
class Solution { public: int majorityElement(vector<int>& nums) { sort(nums.begin(),nums.end()); return nums[nums.size()/2]; } };
3.法二：摩尔投票法（Boyer-Moore）
求众数可以使用摩尔投票法，它基于一个事实——每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个（不证明）。
当遇到与候选人candidate相同的数时，则票数count累加1，否则（不同则）票数累减1。
当票数count为0时，更换候选人，并将票数count重置为1。
class Solution { public: int majorityElement(vector<int>& nums) { int candidate=nums[0]; int count=1; for(int i=1;i<nums.size();i++){ if(candidate==nums[i]){ count++;//遇到相同的则票数+1 }else{ //遇到不同 if(--count==0){//票数为0则替换候选人 candidate=nums[i]; count=1;//重置1 } } } return candidate; } };
