LeetCode-Top100 之 169.多数元素

欢迎关注公众号号，更多C/C++ 学习内容，欢迎一起进步，一起学习。

题目

169.多元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

思路

使用一个map表 <int, int > 第一个int 表示元素，第二个int表示该元素出现的次数
遍历数组中的元素，在map中寻找
如果找到该元素 后面次数加1
如果找不到该元素，说明该元素第一次出现，插入到map中，次数为1

答案

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map <int , int >  retmap;
        for (int i = 0; i < nums.size(); i++)
        {
            map<int,int>::iterator it = retmap.find(nums[i]);
            if(it == retmap.end())
            {   

                retmap.insert({nums[i],1});
            }
            else
            {
                it->second += 1;
                if(it->second > nums.size()/2)
                {
                    return it->first;
                }
            }
         }
      return nums[0];
    }
};