一、题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
二、解题思路 & 代码
2.1 哈希表
因为超过一半，那也就是数量最多的那个元素（都超过一半了，不会再有超过一半的数了）
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if not nums:
return None
num_dict = {
}
max_count, max_num = 0, nums[0]
for num in nums:
if num not in num_dict:
num_dict[num] = 1
else:
num_dict[num] += 1
if num_dict[num] > max_count:
max_count = num_dict[num]
max_num = num
return max_num
- 时间复杂度 O(N)
- 空间复杂度 O(N)
2.2 排序法
将数组 nums 排序，由于众数的数量超过数组长度一半，因此 数组中点的元素 一定为众数。
class Solution:
def majorityElement(self, nums):
nums.sort()
return nums[len(nums)//2]
复杂度分析
- 时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
- 空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。如果自己编写堆排序，则只需要使用 O(1) 的额外空间。
参考：堆排序
2.3 摩尔投票法：
核心理念为 “正负抵消” ；时间和空间复杂度分别为 O(N) 和 O(1) ；是本题的最佳解法。
票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和>0 。
票数正负抵消： 设数组 nums 中的众数为 x ，数组长度为 n 。若 nums 的前 a 个数字的 票数和 =0 ，则 数组后 (n−a) 个数字的 票数和一定仍 >0 （即后(n−a) 个数字的 众数仍为 x ）。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
votes = 0
for num in nums:
if votes == 0:
x = num
votes += 1 if num == x else -1
return x
复杂度分析：
- 时间复杂度 O(N) ： N 为数组 nums 长度。
- 空间复杂度 O(1) ： votes 变量使用常数大小的额外空间。
===================================================
题目拓展：
由于题目明确给定 给定的数组总是存在多数元素 ，因此本题不用考虑 数组中不存在众数 的情况。
若考虑，则需要加入一个 “验证环节” ，遍历数组 nums 统计 x 的数量。
-
若 x 的数量超过数组长度一半，则返回 x ；
-
否则，返回 0 （这里根据不同题目的要求而定）。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
votes, count = 0, 0
for num in nums:
if votes == 0: x = num
votes += 1 if num == x else -1
# 验证 x 是否为众数
for num in nums:
if num == x: count += 1
return x if count > len(nums) // 2 else 0 # 当无众数时返回 0
时间复杂度仍为 O(N)
空间复杂度仍为 O(1)
京公网安备 11010502036488号