0169. 多数元素

本文主要是介绍0169. 多数元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 169. 多数元素

思路

利用哈希表计数，遍历一遍数组此时时间复杂度为$O(n)$，空间复杂度为$O(n)$。

参考K神学会摩尔投票法

这个方法思想很简单，就是模拟投票，且正负票抵消。在本题中，首先假定一个多数元素，遍历元素，如果元素等于多数元素啧票数加1，否则减一。

解题方法

摩尔投票法

初始化：vetoes=0：票数， x=-1：多数元素
依次遍历元素，如果元素等于x，则票数加1，即vetoes+=1
否则，票数减1，即vetoes-=1
当票数为0时，x就是当前遍历到的元素。
返回最后一个x即可。

复杂度

时间复杂度: $O(n)$ 一次遍历

空间复杂度: $O(1)$ vetoes和x中间变量

Code

class Solution:def majorityElement(self, nums: List[int]) -> int:votes = 0 # 票数x = -1 # 众数，这里与数学定义不同，指的是出现次数大于n // 2的元素for i in nums:if votes == 0:x = i # 记votes=0的情况下的当前数字为众数if i == x:votes += 1else:votes -= 1# 若题目没有规定【给定的数组总是存在多数元素】# 需要判断一下x是否为众数cnt = 0for i in nums:if i == x:cnt += 1return x if cnt > len(nums) // 2 else -1

这篇关于0169. 多数元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---