【LeetCode】169. 求众数

末蓝、 2022-05-08 06:52 170阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/majority-element/description/][https_leetcode-cn.com_problems_majority-element_description]

#### 题目描述 ####

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

#### 示例 ####

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

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

#### 解决方法 ####

有三种方法可解此题：  
方法1，因为这里的众数不是指出现次数最多的数，而是指数组中出现次数大于数组数量一半的元素，可以先将数组按升序顺序排序，找出数组中中间元素即可。  
方法2，用map容器建立key,value对，保存每个值出现的次数，找出出现次数大于n/2即可。  
方法3，摩尔投票法

class Solution { 
    public:
        int majorityElement(vector<int>& nums) { 
    // 解法1：因为这里的众数不是指出现次数最多的数，而是指数组中出现次数大于数组数量一半的元素，可以先将数组按升序顺序排序，找出数组中中间元素即可。 
            // sort(nums.begin(),nums.end());
            // return nums[nums.size()/2];
            
            
    // 解法2：用map容器
    // map<int, int> times;
    // for (int i=0;i<nums.size();i++)
    // times[nums[i]]++;
            
    // for(int i=0;i<nums.size();i++)
    // { 
    // if(times[nums[i]]>nums.size()/2) return nums[i];
    // }
    
    // 解法3：摩尔投票法,核心思想是同加、异减 https://www.hijerry.cn/p/45987.html
            int result, score=0;
            for (int i=0;i<nums.size();i++){ 
                if (result==nums[i]) score++;
                else if (score==0) { result=nums[i];score=1;}
                else score--;
            }
            return result;
        }
    };

[https_leetcode-cn.com_problems_majority-element_description]: https://leetcode-cn.com/problems/majority-element/description/