题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

假设数组非空，并且一定存在满足条件的数字。

样例

思考题：

假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
样例
输入：[1,2,1,1,3]

输出：1

C++ 代码

class Solution {
public:
    map<int, int> mp;
    int moreThanHalfNum_Solution(vector<int>& nums) {
        for (unsigned i = 0;i < nums.size(); i ++) {

          if (mp[nums[i]] != 0) {
            mp[nums[i]] ++;

            if (mp[nums[i]] > nums.size() / 2) return nums[i];
          }
          else{
            mp[nums[i]] = 1;

            if (mp[nums[i]] > nums.size() / 2) return nums[i];
          }

        }
    }
};