[LeetCode] 169

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.

class Solution {
public:
　　int majorityElement(vector<int>& nums) {
#if 0
　　　　std::sort(nums.begin(), nums.end());
　　　　return nums[nums.size() / 2 ];
#else
　　　　unordered_map<int, int> maps;
　　　　int times = (nums.size() + 1) / 2;
　　　　for (auto c : nums) {
　　　　　　maps[c]++;
　　　　　　if (maps[c] >= times) {
　　　　　　　　return c;
　　　　　　}
　　　　}
#endif
　　}
};