Majority Element
你会得到一个长度为 n 的整数数组 nums。其中有一个值出现的次数超过 n / 2，这个值称为多数元素。请返回这个值。出现次数超过数组一半的值总是唯一的，因此答案恰好只有一个。
函数
- numsinteger-array
- 整数数组，其中一个值占据了数组中超过一半的位置
- 返回值integer
- 出现次数超过 n / 2 次的值
约束条件
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 有一个值出现的次数超过
nums.length / 2。
示例
- 输入
- nums = [3, 9, 3, 3, 4]
- 输出
- 3
- 解释
- 5 个元素中有 3 个 3。3 大于 5 / 2 = 2.5，而 9 和 4 各出现一次。
- 输入
- nums = [8, 8, 1, 1, 8, 1, 8]
- 输出
- 8
- 解释
- 8 出现了 4 次，1 出现了 3 次。7 个元素中，出现次数超过 3.5 次的元素最多，因此 8 是多数元素，不过在数组的大部分部分中，1 的出现次数也紧跟着 8。
进阶
你能否在 O(n) 时间内，使用 O(1) 的额外内存，找出每个出现次数超过 n / 3 的值？
提示
逐个打开提示，每个都会多透露一点。
统计每个值都能实现，但这需要额外的内存。多数元素有什么特别之处？比较它出现的次数和所有其他值出现次数的总和。
将多数元素的每个副本分别与一个不同的值配对，并把两者都划掉。多数元素的数量比其他所有元素都多，因此无论怎样配对，总会有一些副本留下来。
保留一个候选元素和一个计数器。元素与候选元素匹配时，计数器加 1；不匹配时，计数器减 1。当计数器为 0 时，下一个元素就成为候选元素。最后留下的候选元素就是答案。
题解
数量最多的值比其他所有值加起来还多。划掉一对不同的值后，它总会有一些副本留下来。Boyer-Moore 投票法用一个候选值和一个计数器，在一次遍历中完成这种配对，因此你不需要用哈希映射来统计数量。
使用哈希映射计数
思路
统计哈希映射中每个值出现的次数，并返回出现次数超过长度一半的第一个值。对于 [3, 9, 3, 3, 4]，3 的出现次数在索引 3 处达到 3，超过 2.5，因此你会在读取 4 之前返回。
平均每次查找的时间复杂度为 O(1)，因此总时间复杂度为 O(n)，但映射可能存储约 n / 2 个不同的值：空间复杂度为 O(n)。
算法
- 创建一个从值映射到计数的空映射。
- 对于每个元素
x，将x的计数加 1。 - 如果该计数乘以 2 大于数组的长度，则返回
x。
def majorityElement(nums):
counts = {}
for x in nums:
counts[x] = counts.get(x, 0) + 1
if counts[x] * 2 > len(nums):
return xBoyer-Moore 投票算法
思路
保留一个candidate，并用count记录它尚未被抵消的票数。与候选值相同的元素会增加一票。不同的元素会抵消一票，两者都退出竞争。当计数为 0 时，下一个元素就成为候选值。
每次抵消都会移除两个不同的值，因此至多抵消一个多数值副本。如果多数值出现了m次，其他n - m个元素的数量少于m，无法抵消所有多数值副本。最后仍保留的每一票都属于最终候选值，其中必定包含一个多数值副本。
对于[8, 8, 1, 1, 8, 1, 8]，当值为 1 的元素抵消两个 8 时，计数依次变为 1、2、1、0。下一个 8 会将计数重置为 1，下一个 1 抵消它，最后一个 8 再次成为候选值。只需遍历一次并使用两个变量，时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 将
candidate设为第一个元素，并将count设为 0。 - 对于每个元素
x，如果count为 0，就将x设为候选元素。 - 如果
x等于候选元素，就将count加 1。否则减 1。 - 遍历完最后一个元素后，返回
candidate。
def majorityElement(nums):
candidate = nums[0]
count = 0
for x in nums:
if count == 0:
candidate = x # the old candidate's votes are used up
if x == candidate:
count += 1
else:
count -= 1 # x and one copy of the candidate cancel out
return candidate
易错点和边界情况
- “超过一半”是严格的条件。
count >= n / 2会把 4 个元素中出现 2 次的情况也算进去，但这并不构成多数。比较count * 2 > n，这样就不会受到舍入影响。 - 把最后的
count当作多数元素的出现次数。对于[8, 8, 1, 1, 8, 1, 8]，它最终会变成 1，而 8 出现了 4 次。 - 从
candidate = nums[0]和count = 1开始，然后从索引 0 开始循环。第一个元素会投两次票：对于[1, 2, 2]，计数最终会变成 0，你会返回 1。
常见问题3
Majority Element 的时间复杂度和空间复杂度是多少？
Boyer-Moore 投票算法的时间复杂度为 O(n)，额外空间复杂度为 O(1)。使用哈希映射计数的时间复杂度也是 O(n)，但需要 O(n) 的空间来存储计数。先排序的时间复杂度为 O(n log n)。
可以通过排序来解决多数元素问题吗？
是的。排序后，所有多数元素的副本都会集中在一个长度超过数组一半的区块中，而且任何这样的区块都包含中间位置。因此，索引为 n / 2（向下取整）的元素就是答案，时间复杂度为 O(n log n)。
如果数组可能没有多数元素，该怎么办？
Boyer-Moore 总是会返回一个候选值：对于 [1, 2, 3]，它会返回 3。添加第二遍来统计候选值的出现次数，只有当次数大于 n / 2 时才接受它。总时间复杂度仍为 O(n)，空间复杂度为 O(1)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def majorityElement(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [3, 9, 3, 3, 4]
预期输出
3