python求众数代码_python-LeetCode-求众数
题⽬：给定⼀个⼤⼩为 n 的数组，到其中的众数。众数是指在数组中出现次数⼤于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是⾮空的，并且给定的数组总是存在众数。
⽰例 1:
输⼊: [3,2,3]
输出: 3
⽰例 2:
输⼊: [2,2,1,1,1,2,2]
输出: 2
众数——众数(Mode)是统计学名词，在统计分布上具有明显集中趋势点的数值，代表数据的⼀般⽔平(众数可以不存在或多于⼀个)。 修正定义：是⼀组数据中出现次数最多的数值，叫众数，有时众数在⼀组数中有好⼏个。⽤ M 表⽰。 理性理解：简单的说，就是⼀组数据中占⽐例最多的那个数。
(来⾃百度)
我的解法：利⽤字典，计算每⼀个数字出现的次数，出现次数最⼤的那个就是要求的众数，但是根据题⽬，次数还要⼤于列表长度的⼀半，所以有了下⾯的⽅法：
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dict={x:0 for x in nums}
for x in nums:
dict[x]+=1
for x in dict.key():
if dict[x]>len(nums)//2:
return x
这种⽅法我借鉴了昨天的字典法，利⽤字典来计数。利⽤了额外字典空间，遍历列表⼀次，字典⼀次。
当然，昨天的count法也能完成，这题虽然没有明确要求，但是我们总是要利⽤更⼩的时空复杂度来完成算法。
还有⼀种⽅法，我是没想到，我发现⼤学上久了，那种投机取巧的本事丢了，思维有些不太灵活了，可能是不太动脑⼦了吧。。
这种⽅法利⽤了这样的⽅法，将给的列表排序，因为众数的数量超过⼀半，所以排序后，中间的数⼀定是那个众数。只能说我的脑⼦不⾏。
python 定义数组class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return nums[len(nums)//2]
还有⼀个我刚学会的⽅法——摩尔投票法
我借鉴了⽹上的解释：摩尔投票法的基本思想很简单，在每⼀轮投票过程中，从数组中出⼀对不同的元素，将其从数组中删除。这样不断的删除直到⽆法再进⾏投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的⼀半。如果只存在⼀种元素，那么这个元素则可能为⽬标元素。
⽂章写的Java实现
但是我们不能真的去每次删除两个不相同的值，当然如果你要写也能写出来，这有个更好的⽅法：
从第⼀个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能到最多的那个。——YourBaymax
现在我们来⽤python来实现它：
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count=0
now=None
max=len(nums)/2
for i in nums:
if count==0:
now=i
count=1
elif count>max:
return now
elif i==now:
count+=1
else:
count-=1
return now
这种⽅法是最快的，⽽且，只⽤了常数个空间来保存计数和待选众数。
厉害！！这种⽅法我看了挺久的，脑⼦不⾏了。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。