难度: Easy
仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。
示例 1:
输入: stock = [6, 1, 3, 1, 1, 1] 输出: 1
限制：
1 <= stock.length <= 50000注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/
运行时间: 52 ms
内存: 16.1 MB
class Solution:
def majorityElement(self, nums: List[int]) -> int:
c = 1
m = nums[0]
for num in nums[1:]:
if num == m:
c += 1
else:
c -= 1
if c <= 0:
c = 1
m = num
return m
if __name__ == '__main__':
s= Solution()
s.majorityElement([3, 3, 4])
该题解使用了摩尔投票算法（Boyer-Moore Voting Algorithm），这是一种用于寻找数组中出现次数超过一半的元素的有效方法。算法的核心思想是维护一个候选元素和一个计数器。遍历数组时，如果计数器为0，则将当前元素设为候选元素并将计数器设为1。如果当前元素等于候选元素，则增加计数器；如果不等，则减少计数器。这样，最后剩下的候选元素就是出现次数超过一半的元素。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
c = 1 # 初始化计数器为1
m = nums[0] # 初始化候选元素为第一个元素
for num in nums[1:]: # 从第二个元素开始遍历
if num == m:
c += 1 # 如果当前元素等于候选元素，增加计数器
else:
c -= 1 # 如果当前元素不等于候选元素，减少计数器
if c <= 0:
c = 1 # 如果计数器小于等于0，更新候选元素
m = num
return m # 返回候选元素
if __name__ == '__main__':
s = Solution()
s.majorityElement([3, 3, 4]) # 示例调用
摩尔投票算法的更新逻辑是基于一种成对抵消的原理。每次当计数器减为0时，意味着到目前为止的所有元素中，候选元素和其他元素的数量已经完全抵消，因此之前的所有元素都不能确定是多数元素。这时将当前元素设为新的候选元素，并重新开始计数，可以确保如果存在多数元素，它最终会被正确选出。
在摩尔投票算法结束后，候选元素m是基于其出现次数可能超过数组一半的推断。但是，算法本身不保证m一定是多数元素，特别是当输入数组中没有任何元素的出现次数超过一半时。因此，在实际应用中，我们通常需要对候选元素m进行一次遍历验证，确认其出现次数确实超过数组长度的一半，以确保其为多数元素。
如果输入数组中没有任何元素的出现次数超过一半，摩尔投票算法仍然会返回一个候选元素，但这个元素不保证是多数元素，因为实际上不存在多数元素。在这种情况下，算法的候选元素只是最后一次计数器被设置为1时对应的元素。因此，如果数组中不存在多数元素，算法的输出需要通过额外的验证步骤来确认，否则可能会得到错误的结果。