Re: [閒聊] 每日LeetCode
https://leetcode.com/problems/majority-element/description
169. Majority Element
給你一個陣列nums，找出出現次數最多的元素，題目保證有解且元素數量大於n/2。
思路：
1.樸素解是用一個map統計每個數字的出現次數然後找出數量大於n/2的，這類問題可以
用一個特殊演算法Boyer–Moore majority vote algorithm去求解，遇到不同數字就
把票數相互抵銷，如果票數為0就換一個人，因為某個數字數量大於n/2所以最後會找
出Majority Element
py code
--------------------------------------
class Solution:
def majorityElement(self, nums: List[int]) -> int:
major = nums[0]
count = 0
for n in nums:
if count == 0:
count = 1
major = n
elif major == n:
count += 1
else:
count -= 1
return major
--------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707728759.A.CF8.html
討論串 (同標題文章)
完整討論串 (本文為第 672 之 719 篇)：