多数元素 leetcode

leetcode 题库 剑指 Offer 39 数组中出现次数超过一半的数字

使用 摩尔投票法 解决众数问题

一、题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

输出: 2

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以换做下面的方式来理解本体：

二、诸侯争霸游戏：

游戏规则设定：

1、m 个国家进行诸侯争霸；

2、每个国家的士兵人数为 a1,a2……，am,总士兵人数为 a1 + a2 + a3 …… + am 记为 C；

3、其中存在一个国家 i 的士兵人数超过总士兵人数的一半，即 ai > C/2；

4、m 个国家随机的往战场上面投放士兵，并且每个国家每次只能投放一个士兵；

5、只要战场上存在两个不同国家的士兵，那么就会相会搏杀，两个士兵同归于尽；

6、所有的国家都要出动所有的士兵参战，中途不能退出，直至士兵消耗完毕；

7、最后的胜利者属于最后能够生存下来的国家；

则最终的胜利一定属于第 i 个国家，这个国家就是那个士兵数量超过总士兵人数的一半的国家；

三、代码如下：

public int majorityElement(int[] nums) {
    int mode = 0;//士兵数量暂时领先的国家
    int count = 0;//士兵数量暂时领先的数量
    for (int num : nums) {      //每个国家都随机的往战场中投放士兵
        if (count == 0) {       //若战场中不存在士兵
            mode = num;         //投放士兵的国家就变成了  士兵数量暂时领先的国家
        }
        if (mode == num) {      //如果投放的士兵和战场中的士兵来自相同的国家
            count++;            //士兵数量就会 + 1
        } else {                //如果投放的士兵和战场中的士兵来自不同的国家
            count--;            //两个士兵同归于尽 这是会消耗掉 1 个 暂时领先的国家的士兵
        }
    }
    //最后可以生存下来的国家
    return mode;
}

打赏