难度: Easy
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
运行时间: 20 ms
内存: 17.7 MB
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
这个题解采用了摩尔投票算法。该算法的基本思想是用一种有效的方式找出列表中的多数元素。算法维护一个候选多数元素和一个计数器，遍历数组中的每个元素，当计数器为0时，将当前元素作为候选多数元素，并初始化计数器为1。如果遇到的元素等于当前候选元素，则计数器加1，否则计数器减1。由于多数元素的数量大于n/2，所以最后候选元素一定是多数元素。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = 0 # 初始化计数器
candidate = None # 初始化候选多数元素
for num in nums: # 遍历数组中的每个元素
if count == 0: # 当计数器为0时
candidate = num # 更新候选多数元素
count += (1 if num == candidate else -1) # 如果当前元素等于候选元素，计数器加1，否则减1
return candidate # 返回最后的候选多数元素，即多数元素
摩尔投票算法之所以能确保最终候选元素是多数元素，是基于一个关键假设：数组中存在一个元素的数量超过了数组长度的一半。因此，即使在遇到计数器为零时频繁更换候选者的情况下，真正的多数元素由于数量优势，最终会使得计数器的值在算法结束时为正。每次计数器归零时更换候选者，其实是一次重新计数的开始，而真正的多数元素总能在遍历结束时保持计数器为正数，从而成为最终的候选者。
摩尔投票算法的效率主要依赖于遍历数组的次数，其时间复杂度始终是O(n)，即与数组长度成线性关系。多数元素的分布是否均匀并不影响算法的时间复杂度。无论多数元素如何分布，算法都只需要一次遍历即可确定候选者。分布的不均匀可能会导致计数器的变化更加频繁，但这并不影响算法总体的遍历次数和时间复杂度。
摩尔投票算法的前提是存在一个多数元素，即某个元素出现的次数超过数组长度的一半。如果一个数组中所有元素均不相同，则没有任何一个元素的出现次数能超过数组长度的一半。在这种特殊情况下，摩尔投票算法不适用，因为它依赖于多数元素的存在。如果用此算法处理所有元素均不相同的数组，算法会返回一个结果，但这个结果不具有实际意义，因为并不存在一个真正的多数元素。