# 第92期-基础技巧：计数 多数元素
Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。
# 1 问题描述
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: nums = [1]
输出: 1
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
初始代码
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
#在此之间填写代码
print(Solution().majorityElement([3,2,3]))
print(Solution().majorityElement([1]))
print(Solution().majorityElement([1,1,1,3,3,2,2,2]))
2
3
4
5
6
7
8
# 2 解题思路
- 标签：计数
- 思路：摩尔投票法
- 也可以使用哈希表统计，但是这种方式空间复杂度较高。摩尔投票法空间复杂度较低。
- 摩尔投票法的思路：定义两个数字两个count，新元素是其中任意一个数字，则对应的count加一
- 若不等于两者中的任意一个，则两个count都减一
- 最终判断出现次数是否大于1/3
# 3 解题方法
from typing import List
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
if len(nums)<3: return list(set(nums))
n1, cnt1, n2, cnt2 = 0, 0, 0, 0
for n in nums:
if (cnt1==0 or n==n1) and n!=n2:
n1 = n
cnt1+=1
continue
if cnt2==0 or n==n2:
n2 = n
cnt2+=1
continue
cnt1 -= 1
cnt2 -= 1
ans1 = [n1] if(len([i for i in nums if i==n1]) > len(nums)//3) else []
ans2 = [n2] if(len([i for i in nums if i==n2]) > len(nums)//3) else []
return list(set(ans1 + ans2))
print(Solution().majorityElement([3,2,3]))
print(Solution().majorityElement([1]))
print(Solution().majorityElement([1,1,1,3,3,2,2,2]))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
第1-3，22-24行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 特殊情况，当nums长度小于三时，直接返回其没有重复值的新列表
第5行： 定义变量n1，cnt1，n2，cnt2并全部赋值为0
第6行： 使用for循环变量nums中的所有元素
第7-10行： 若cnt1等于0或n1和遍历到的值相等，且不等于n2时，令cnt1加一，结束本次循环
第11-14行： 若cnt2等于0或n2和遍历到的值相等、时，令cnt2加一，结束本次循环
第15-16行： 若便利到的值与两者都不相等，则cnt1和cnt2都减一
第17-18行： 判断最后得到的两个数在nums中出现次数是否超过1/3，若是，则将该数放进列表中，若不是，则列表为空
第19行： 返回最后两个列表相加形成的列表
代码运行结果为：
# 技巧讲解
这里用到了基础技巧：计数：摩尔投票法，简单讲解下这个技巧：
摩尔投票法
摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。
这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。
如果只存在一种元素，那么这个元素则可能为目标元素。
那么有没有可能出现最后有两种或两种以上元素呢？
根据定义，这是不可能的，因为如果出现这种情况，则代表我们可以继续一轮投票。
因此，最终只能是剩下零个或一个元素。
# 4 视频解析
高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码 