力扣刷题（第三十六天）
灵感来源
- 保持更新，努力学习
- python脚本学习
多数元素
解题思路
这道题是要找出数组中出现次数超过一半的元素。有几种不同的方法可以解决这个问题：
-
哈希表统计法：遍历数组，用哈希表统计每个元素的出现次数，然后找出次数超过一半的元素。时间复杂度和空间复杂度都是 O (n)。
-
排序法：如果将数组排序，那么下标为 n/2 的元素（n 为数组长度）一定是众数。时间复杂度取决于排序算法，通常是 O (n log n)，空间复杂度 O (1)（如果是原地排序）。
-
摩尔投票法：这是一种非常巧妙的算法，时间复杂度 O (n)，空间复杂度 O (1)。它的核心思想是：在每一轮投票过程中，从数组中找出一对不同的元素并删除，直到数组为空或只有一种元素。由于众数的出现次数超过一半，因此最终剩下的元素一定是众数。
class Solution:def majorityElement(self, nums: List[int]) -> int:count = 0candidate = Nonefor num in nums:if count == 0:candidate = numcount += (1 if num == candidate else -1)return candidate
逐行解释
class Solution:def majorityElement(self, nums: List[int]) -> int:# 初始化计数器为0count = 0# 初始化候选众数为Nonecandidate = None# 遍历数组中的每个元素for num in nums:# 当计数器为0时，意味着之前的候选众数已被抵消完# 此时将当前元素设为新的候选众数if count == 0:candidate = num# 如果当前元素等于候选众数，计数器加1# 否则计数器减1（相当于一对不同元素相互抵消）count += (1 if num == candidate else -1)# 由于众数出现次数超过一半，最终候选众数即为所求众数return candidate