# 【LeetCode】 169. Majority Element

## Description
> 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.

> 給一個大小為n的陣列，請找到它的主要元素。主要元素指它出現的次數大於 ⌊ n/2 ⌋ 次的元素。

> 你可以假設陣列不會是空的，且主要元素總是存在於陣列中。

## Example:

Example 1:

Input: [3,2,3]
Output: 3


Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

## Solution

* 方法一：hash table去存元素出現的次數，較節省時間。
* 方法二：先排序，再直接回傳陣列最中間的數，較節省空間。

### Code

- 方法一：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> hash;
        int s = nums.size();
        for(int i=0;i<s;i++)
        {
            if(++hash[nums[i]] > s/2)
                return nums[i];
        }
        return -1;
    }
};

- 方法二：

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

###### tags: `LeetCode` `C++`