【LeetCode】169. 求众数-蒲公英云

【LeetCode】169. 求众数

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

题目链接：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;
    }
};