题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
- 输入：[1,2,5,9,5,9,5,5,5]
- 输出：5
示例 2：
- 输入：[3,2]
- 输出：-1
示例 3：
- 输入：[2,2,1,1,1,2,2]
- 输出：2
题目思考
- 如何不使用额外空间?
- 如何识别不存在主要元素的情况?
解决方案
思路
- 一个最简单的思路是用一个计数字典存每个数字的出现次数, 找最大的那个即可, 但这需要额外的空间, 不是面试官心目中的理想答案
- 重新分析题目, 某个数字出现超过一半, 那意味着其他数字的数目之和都小于它, 如果我们将这些不同数字进行两两抵消, 那么最后剩余的那个数字一定是超过一半的那个数字, 这就引出了下面的思路:
- 维护一个当前候选者, 以及当前它的计数, 初始化就是数组头一个数字, 计数为 1
- 从第二个数字开始遍历数组, 如果当前数字等于候选者, 那么计数值加 1, 否则就减 1 表示抵消了一个数字
- 如果此时计数小于 0 的话, 就说明之前的候选者这个时候要被淘汰了, 因为它已经被抵消光了. 所以就重新选择当前的数字作为新的候选者, 同时重置计数值为 1.
- 这样最后剩余的那个候选者就可能是最终结果
- 注意上面第 4 步说的是可能而不是一定, 举个例子, 对于数组
[1,2,3], 利用此方法得到的最终候选者为 3, 但它并不是主要元素, 只是恰好最后一个被选出来的候选者而已 - 所以我们在得到最终候选者之后, 需要重新遍历一遍数组并累加其计数, 确保其计数超过一半
- 不然的话就说明整个数组没有主要元素, 返回 -1 即可
复杂度
- 时间复杂度
O(N): 只需要遍历数组一遍 - 空间复杂度
O(1): 只使用了几个变量
代码
class Solution:
def majorityElement(self, nums: List[int]) -> int:
# 候选主要元素
major = 0
# 主要元素的计数
cnt = 0
for x in nums:
if x == major:
# 当前元素就是major, 增加计数
cnt += 1
elif cnt == 0:
# 当前计数是0, 改用当前元素
major = x
cnt += 1
else:
# 当前元素不是major, 减少计数
cnt -= 1
# 统计major的实际计数
cnt = len([x for x in nums if x == major])
# 只有当实际计数超过一半才说明是真正的主要元素
return major if cnt > len(nums) / 2 else -1
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号