刷题之多数元素（leetcode）

多数元素

哈希表解法：

class Solution {
public:/*int majorityElement(vector<int>& nums) {//map记录元素出现的次数，遍历map，求出出现次数最多的元素unordered_map<int,int>map;for(int i=0;i<nums.size();i++){map[nums[i]]++;}int max=0;int result=0;for(auto iterator=map.begin();iterator!=map.end();iterator++){if(iterator->second>max){max=iterator->second;result=iterator->first;}}return result;}*/int majorityElement(vector<int>& nums) {//map记录元素出现的次数，遍历map，求出出现次数最多的元素unordered_map<int,int>map;int max=0;int result=0;for(int i=0;i<nums.size();i++){map[nums[i]]++;if(map[nums[i]]>max){max=map[nums[i]];result=nums[i];}}return result;}
};

效率更高的解法：

class Solution {
public:int majorityElement(vector<int>& nums) {//因为多数元素出现次数大于n/2，所以多数元素与非多数元素次数相消还是多数元素，类比正负电子（labuladong题解解释）int count=0;int target=0;for(int i=0;i<nums.size();i++){if(count==0){target=nums[i];count++;}else {if(nums[i]==target){count++;}else if(nums[i]!=target){count--;}}}return target;}
};