【LeetCode】169. Majority Elementを解く

問題へのリンク

問題概要

サイズ$n$の配列numsが与えられるので，過半数を占める要素を返す．

このとき，過半数を占める要素とは$floor(n/2)$回より多く出現する要素のことであり，配列の中に必ず存在すると仮定して良い．

例：

Input: nums = [3,2,3]
Output: 3

制約

• $n == nums.length$
• $1 \leq n \leq 5*10^4$
• $-2^{31} \leq nums[i] \leq 2^{31} -1$

考えたこと

$1 \leq n \leq 5*10^4$なので$O(n)$でも十分に間に合いそうなので，

• 各要素を順にみていき，出現回数をカウント
• その中から過半数以上出現する要素を探す

の手順で解を求められる：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        border = len(nums)//2
        dict = defaultdict(int)
        
        for n in nums:
            dict[n] += 1
            if dict[n] > border:
                return n

Tips

実は，この問題には線形時間かつ$O(1)$の空間で解くという制約下でのフォローアップ問題がある．

このアルゴリズムはMooreさんが考案したもので以下のサイトで紹介されている：

• Boyer-Moore Majority Vote Algorithm

このアルゴリズムを参考にした解答は以下の通り：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        counter = 0
        res = nums[0]
        for n in nums:
            if counter == 0:
                res = n
                counter += 1
            else:
                if res == n:
                    counter += 1
                else:
                    counter -= 1            
        return res