本文共 1193 字，大约阅读时间需要 3 分钟。

LeetCode.jpg

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]

输入: [2,2,1,1,1,2,2]

Python3 实现

排序法

# @author:leacoder# @des:  排序法 求众数  时间复杂度 O（nlg(n)）class Solution:    def majorityElement(self, nums: List[int]) -> int:         nums.sort()        return nums[int(len(nums)/2)]  #条件>n/2，所以排序后，中间元素一定是众数

dic计数

# @author:leacoder# @des:  dic 求众数class Solution:    def majorityElement(self, nums: List[int]) -> int:         dic = {}        for num in nums:            if num in dic:                dic[num] = dic[num]+1            else:                dic[num] = 1        length = len(nums)        for num in dic:            if dic[num]>int(length/2):                return num

摩尔投票法

# @author:leacoder# @des:  摩尔投票法 求众数class Solution:    def majorityElement(self, nums: List[int]) -> int:         moore = 0        count = 0        for num in nums:  #由于给定的数组总是存在众数。 众数 与 非众数 抵消后最后 count必然>0            if count == 0:                moore = num #最终 moore 存放的就是众数            if num == moore:                count +=1  #重复一次 +1            else:                count -=1 #出现其他数据 -1        return moore

GitHub链接：

知乎个人首页：

个人Blog:

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/101467138 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！