Majority Element

题目：

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.

分析：

上来就想到利用map

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         size_t m = nums.size() / 2;
 5         map<int,int> nums_count;
 6         vector<int>::iterator it = nums.begin();
 7         while(it != nums.end())
 8             nums_count[*it++]++;
 9         map<int,int>::iterator it2 = nums_count.begin();
10         while(it2 != nums_count.end())
11         {
12             if( it2->second > m)
13                 return it2->first;
14             it2++;
15         }
16     }
17 };

另一种思路，好像比我的慢

1 int majorityElement1(vector<int>& nums) {
2     sort(nums.begin(), nums.end());
3     return nums[nums.size()/2];
4 }