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

喜欢ヅ旅行 2022-11-21 01:23 99阅读 0赞

# 题目 #

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

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

示例 1:

> 输入: \[1, 2, 3, 2, 2, 2, 5, 4, 2\]  
> 输出: 2

限制：

*  1 <= 数组长度 <= 50000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof][https_leetcode-cn.com_problems_shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof]

# 解题思路 #

题目约定:给定的数组总是存在多数元素  
本题的最优解法就是摩尔投票

摩尔投票，其实就是诸侯乱战，你作为东方大国，拥有超过总数 1/2 的兵力，且规定一个兵打一个兵必定同归于尽，那么即使全部诸侯打你一个，最后剩下的兵肯定也是你的兵，也就是你赢了。

# 代码 #

class Solution { 
        public int majorityElement(int[] nums) { 
            // 摩尔投票
            // 众数
            int x = 0;
            // 投票
            int votes = 0;
            for (int num : nums) { 
                // 如果投票数为0,则把当前数当做众数
                if (votes == 0) { 
                    x = num;
                }
    
                // 判断当前数和众数是否相等
                // 相等,票数+1
                // 不相等,票数-1
                votes += (x == num ? 1 : -1);
            }
            return x;
        }
    }

# 复杂度 #

*  时间复杂度:O(n),循环一遍数组
 *  空间复杂度:O(1),常数级额外空间

[https_leetcode-cn.com_problems_shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof