C++速通LeetCode简单第20题-多数元素

方法一：暴力解法，放multiset中排序，然后依次count统计，不满足条件的值erase清除。 

class Solution {
public:int majorityElement(vector<int>& nums) {int ans = 0;multiset<int> s;for(int i = 0;i < nums.size(); i++){s.insert(nums[i]);}for(multiset<int>::iterator it = s.begin();it != s.end();it++){if(s.count(*it) > nums.size() >> 1){ans = *it;break;}else s.erase(*it);//消除不是最多的重复元素，提高效率it = s.begin();//迭代器转到消除后的第一个元素}return ans;}
};

方法二：最优解法，摩尔投票法，转换为投票选举问题，最后票数多的为答案。

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = -1;int count = 0;for (int num : nums) {if (num == candidate)++count;else if (--count < 0) {candidate = num;count = 1;}}return candidate;}
};

纪念：这是100题的最后一道简单题啦，下面就要进军中等题咯，加油。