### 问题描述

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

### 思路

1. Hash表计数法：用一个Hash表记录每个元素出现的次数
2. Moore voting algorithm：记录元素elem，计数器counter，遍历数组，如果counter为0，则elem为当前元素；如果counter不为0，若elem==当前元素，counter++，若elem!=当前元素，counter--，最终的elem一定输Majority元素。因为一定会出现Majority元素，所以它的元素个数是大于n/2的，假设有k个，其余元素有m个，肯定有 k>m，所以最终计数下来，剩下的那个肯定是Majority元素

### 代码

1 Hash表计数法

class Solution {
public:

int majorityElement(vector<int>& nums) {
map<int, int> counts;
for (int i = 0; i<nums.size(); i++) {
if (counts.find(nums[i]) == counts.end()) {
counts[nums[i]] = 0;
}
counts[nums[i]]++;
if (counts[nums[i]]>nums.size() / 2) {
return nums[i];
}
}
return 0;
}
}


2 Moore voting algorithm

class Solution {
public:

int majorityElement(vector<int>& nums) {
int count = 0;
int elem = 0;
for (int i = 0; i<nums.size(); i++) {
if (count == 0) {
elem = nums[i];
count++;
}
else {
if (elem == nums[i]) {
count++;
}
else {
count--;
}
}
}
return elem;
}
}