169. Majority Element

Given an array of sizen, find the majority element. The majority element is the element that appearsmore than n/2 times.

You may assume that the array is non-empty and the majority element always exist in the array.


思路1：

使用map来处理。

classSolution{public:intmajorityElement(vector<int>&nums){map<int,int>record;for(inti=0;i<nums.size();i++){if(record.find(nums[i])==record.end()){record.insert(pair<int,int>(nums[i],1));if(record[nums[i]]>nums.size()/2){returnnums[i];}}else{record[nums[i]]+=1;if(record[nums[i]]>nums.size()/2){returnnums[i];}}}return0;}};

思路2：

采用双循环

intmajorityElement(vector<int>&nums){inthit=0;intcurrentElem;for(inti=0;i<nums.size();i++){currentElem=nums[i];hit=0;for(intj=0;j<nums.size();j++){if(nums[j]==currentElem){hit++;if(hit>nums.size()/2){returncurrentElem;}}}}return0;}


2016-08-10 12:19:37