Leetcode：【169. 多数元素】-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode：【169. 多数元素】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

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

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

难度：简单

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

Leetcode：【169. 多数元素】,【leetcode】题解,leetcode,算法,c语言文章来源地址https://www.toymoban.com/news/detail-698355.html