[leetcode刷题]面试经典150题之5多数元素元素（简单）【附Boyer-Moore 投票算法（摩尔投票法）】

很有意思的一个题，想了半天没想出来，最后发现两行代码就做出来了。写完后学习到还可以用Boyer-Moore 投票算法，能减小空间复杂度，我把它写在后面，可以进一步学习。

题目多数元素

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

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

解决思路

这个题的重点是多数元素大于总元素的n/2，也就是说这个数组中超过一半的数都是这个数。那么我们可以将元素排序，无论n为奇还是偶，int(n/2)的位置一定是这个多数元素。

代码

class Solution:def majorityElement(self, nums: List[int]) -> int:nums.sort()return nums[int(len(nums)/2)]

Boyer-Moore 投票算法详解

Boyer-Moore 投票算法是一种用于寻找多数元素的经典算法。它可以在 O(n) 的时间复杂度和 O(1) 的空间复杂度下找到数组中的多数元素。

多数元素定义：

多数元素是指在一个长度为 n 的数组中，出现次数超过 n/2 的元素。例如，在数组 [3, 3, 4, 2, 3, 3, 3] 中，元素 3 是多数元素，因为它出现了 5 次，超过了数组长度的一半（7 / 2 = 3.5）。

算法思路：

Boyer-Moore 投票算法基于一个简单但有效的贪心思想：通过配对和抵消的方式找到多数元素。具体过程如下：

假设：我们假设数组中确实存在一个多数元素，它的出现次数大于 n/2。
配对与抵消：
- 初始化一个候选元素，并设置它的计数器为 1。
- 遍历数组，当遇到与当前候选元素相同的元素时，增加计数器；当遇到不同的元素时，减少计数器。
- 如果计数器为 0，意味着当前候选元素的力量被完全抵消掉了，我们选择当前的元素作为新的候选元素，并将计数器重置为 1。
最终结果：遍历结束后，剩下的候选元素就是多数元素。

代码

class Solution:def majorityElement(self, nums: List[int]) -> int:candidate = None  # 初始化候选元素count = 0  # 计数器# 第一遍遍历找出候选元素for num in nums:if count == 0:  # 如果计数为0，更新候选元素candidate = numcount += (1 if num == candidate else -1)  # 相同则+1，不同则-1# 返回最终的候选元素return candidate

学习这个算法的时候我有想会不会有有特殊情况使多数元素最后结果也是0，例如多数元素没隔一个出现一次的情况会什么样？会不会就不行了。答案是并不会，例如数组 [1, 3, 1, 3, 1, 3, 1]，也可以通过 Boyer-Moore 投票算法找到多数元素。我们来看看这个过程如何进行。

nums = [1, 3, 1, 3, 1, 3, 1]

初始化 candidate = None，count = 0。
遍历 nums：
- 第一个元素 1，count == 0，所以 candidate = 1，count = 1。
- 第二个元素 3，不同于 candidate，所以 count = 0。
- 第三个元素 1，count == 0，candidate = 1，count = 1。
- 第四个元素 3，不同于 candidate，count = 0。
- 第五个元素 1，count == 0，candidate = 1，count = 1。
- 第六个元素 3，不同于 candidate，count = 0。
- 第七个元素 1，count == 0，candidate = 1，count = 1。