[LeetCode] 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存储数组中元素及其出现的次数，通过map中元素的出现次数找出众数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int num : nums)
            m[num]++;
        for (auto it = m.begin(); it != m.end(); it++)
            if (it->second > nums.size() / 2)
                return it->first;
    }
};
// 23 ms

也可以将数组排序，因为众数是在数组中出现⌊ n/2 ⌋的元素，所以在排序后数组的中间位置的元素一定是众数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};
// 23 ms