Leetcode：【169. 多数元素】

短命女 2023-10-15 10:43 10阅读 0赞

**题目**

> 给定一个大小为 `n`的数组 `nums` ，返回其中的多数元素。多数元素是指在数组中出现次数 **大于** `⌊ n/2 ⌋` 的元素。
> 
> 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
> 
> 难度：简单
> 
> 题目链接：[169. 多数元素][169.]

**示例 1：**

输入：nums = [3,2,3]
    输出：3

**示例 2：**

输入：nums = [2,2,1,1,1,2,2]
    输出：2

**提示：**

*  `n == nums.length`
 *  `1 <= n <= 5 * 104`
 *  `-109 <= nums[i] <= 109`

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

**代码展示**

int majorityElement(int* nums, int numsSize){
        int king = nums[0];//假设第一个是多数元素
        int votes = 1;
        int i = 0;
        for( i = 0;i<numsSize;i++)
        {
            if(nums[i] == king)
                votes++;
            else
            {
                votes--;
                if(votes == 0)
                {
                    king = nums[i];//多数元素
                    votes = 1;//票数重置
                }
            }
        }
        return king;
    }

**【解析】**

这里采用的 进阶的做法（时间复杂度为 O(n)、空间复杂度为 O(1) ）

采用的是 **摩尔投票法**

*简单地介绍一下摩尔投票法*

*摩尔投票法：*

*核心就是对拼消耗。*

*玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。*

*那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。*

*最后能剩下的必定是自己人*

其实可以 在nums数组中 元素可以这样区分 友军（相同元素），敌军（不同元素）。遇到相同元素加1，不用元素减1。

![8dcd81b928644539982e10371d9360f2.png][]

[169.]: https://leetcode.cn/problems/majority-element/description/
[8dcd81b928644539982e10371d9360f2.png]: https://img-blog.csdnimg.cn/8dcd81b928644539982e10371d9360f2.png