亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

[leetcode刷題python] 求眾數

系統 1578 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條評論
主站蜘蛛池模板: 久久精品最新免费国产成人 | 国产精品福利资源在线 | 久久亚洲伊人 | 精品自拍视频在线观看 | 香蕉一区二区三区观 | 毛片a级 | 国产午夜精品尤物福利视频 | 久草视频免费在线观看 | 久久亚洲国产伦理 | 91网红福利精品区一区二 | 一级午夜a毛片免费视频 | 久久精品国产2020观看福利色 | 四虎精品成人a在线观看 | 午夜亚洲国产理论秋霞 | 欧美一级欧美三级 | 中文字幕亚洲综合久久202 | 国产99精品一区二区三区免费 | h片在线免费观看 | 国产小视频在线观看免费 | 97人人澡人人爽人人爱 | 国产亚洲欧美在线 | 日韩高清一区 | 99资源在线观看 | 欧美精品在线一区二区三区 | 一级在线视频 | 欧美操穴 | 亚洲欧美一区二区三区在线 | 亚洲日韩欧美综合 | 亚洲精品国产啊女成拍色拍 | 色综合网亚洲精品久久久 | 日本在线高清不卡 | 成年人网站免费 | 五月久久亚洲七七综合中文网 | 狠狠艹| 日本操比 | 在线播放成人毛片免费视 | 99er久久| 久草精品视频在线观看 | 色综合色狠狠天天综合色hd | 亚洲一区在线日韩在线深爱 | 久久精品国产大片免费观看 |