解题思路：

思路一：哈希

1. 遍历数组，将数字映射到哈希数组的元素加一，统计出各数字出现的次数。
2. 遍历哈希数组，选出出现次数超过一半的数字。

思路二：排序取中

1. 数组排序后，如果符合条件的数存在，则一定是数组中间那个数
2. 比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等

题解：

思路一：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        vector<int> hash;
        hash.resize(10000);
        for(auto e : numbers)
        {
            ++hash[e];
        }
        for(size_t i = 0; i<hash.size(); ++i)
        {
            if(hash[i] > numbers.size()/2)
            {
                return i;
            }
        }
        return 0;
    }
};

思路二：

class Solution 
{
public:
  int MoreThanHalfNum_Solution(vector<int> numbers) 
  {    
    sort(numbers.begin(),numbers.end()); // 排序，取数组中间那个数
    int middle = numbers[numbers.size()/2];
    return middle;
  }
};

分类标签： #数组# #哈希# #排序#