[leetcode刷题python] 求众数

系统 1387 0

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

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

示例 1:

            
              输入: [3,2,3]
输出: 3

            
          

示例 2:

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

            
          

解法一:

满足题干要求的众数若存在,则仅可能存在一个

  • 用dict来存储每个数字出现的次数
  • 根据出现次数排序
  • 判断出现次数最多的元素,其出现次数是否超过len/2 +1
python代码:
            
              class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        cnt = length // 2 + 1
        cnt_dict = {}
        
        for i in nums:
            if i in cnt_dict:
                cnt_dict[i] += 1
            else:
                cnt_dict[i] = 1
        cnt_dict = sorted(cnt_dict.items(), key=lambda x:x[1])
        print(cnt_dict)
        if cnt_dict[-1][1] >= cnt:
            return cnt_dict[-1][0]
        else:
            return 0

            
          

注意

  • python中的sorted()函数可以对list和dict排序,对list排序比较简单:
            
              x = [1,3,4,2]
y = sorted(x)

            
          

输出为

            
              y = [1,2,3,4]

            
          

对dict排序时需要制定按照哪个值来排序,并且返回的是一个list,详见:
https://www.runoob.com/python/python-func-sorted.html

值得注意的是,为了方便起见,这里直接用了dict.items()将dict转换成了一个list

            
              dict = { 'one': 1, 'two': 2}
dict.items() = [('one',1), ('two',2)]

            
          

解法二:

众数出现的次数一定大于其他所有元素出现次数之和

  • 遍历数组,记录两个数res,cnt
  • 若当前元素和res相等,则cnt + 1,不相等则 cnt - 1, cnt等于0时,res等于当前元素
  • 遍历结束后res的值可能为众数,但还需要检查是否满足大于 length/2(因为有可能相等,则不满足)
python代码
            
              class Solution(object):
    def majorityElement(self, nums):
        cnt = 0
        res = nums[0]
        for i in range(len(nums)):
            if cnt == 0:
                res = nums[i]
                cnt = 1
            elif res == nums[i]:
                cnt += 1
            elif res != nums[i]:
                cnt -=1

		# 判断出现次数最多元素的次数是否满足题干要求
        count = 0
        for i in range(len(nums)):
            if nums[i] == res:
                count +=1
        if count > len(nums) / 2:
            return res
        else:
            return 0

            
          

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论