LeetCode 169. Majority Element
class Solution:
def majorityElement(self, nums: List[int]) -> int:
majority = nums[0]
count = 0
for elm in nums:
if majority == elm:
count += 1
else:
if count > 0:
count -= 1
else:
majority = elm
count = 1
return majority
Boyer–Moore多数決アルゴリズムを用いたものらしい。
このアルゴリズムがなぜうまくいくのかを説明しているサイトは見つけられなかったので、コーディング面接の時は他の解法を使うのが良さそう。
例えば。
出現した文字の回数を数えて辞書に入れる。
出現回数が最大の文字はmax(dic, key=dic.get)で取って来られるらしい。