過半数判定アルゴリズム（LeetCode / Majority Elementより）

過半数を獲得した候補者を効率的に特定するにはどんな方法が良いと思いますか？

今日の問題は、そう読み替えてみるとなかなか奥が深いです。

https://leetcode.com/problems/majority-element/

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:
Input: [3,2,3]
Output: 3

Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

n個の値からなるリストについて、n/2回より多く登場する値を特定する問題です。

解答・解説

解法1

アルゴリズムを特段考えないと、辞書を用意して出現回数をカウントし回数の最も多い値を返す、というのが最も思いつきやすい処理でしょうか。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        for n in nums:
            if n not in d.keys():
                d[n] = 1
            else:
                d[n] += 1
        return max(d, key=d.get)

max(d, key=d.get)でvalueの最も大きいkeyを取得することができます。

時間計算量は、空間計算量もです。

解法2

n/2回よりも多く登場するものを見つけるんだから、わざわざ全要素を見なくても良さそうだな、と考えます。
すると、昇順でも降順でも良いですがsortして、中央にある要素を取得すれば、それが最も多く登場する要素になっている、というのがこちらの考え方です。

具体例をあげます。

nが奇数の場合：
nums = [1,1,2,2,2]のとき、nums[2]が2なので答えは2

nが偶数の場合：
nums = [1,2,2,2]のとき、nums[1]もしくはnums[2]が2なので答えは2

以下のようにnが奇数か偶数かで場合分けしても良いのですが、

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        if len(nums) % 2 == 0:
            return nums[len(nums)/2]
        else:
            return nums[(len(nums)-1)/2]

nが奇数でも偶数でも、len(nums)を2で割った商のインデックスを参照すれば良いので、以下のようにシンプルに書けます。

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return nums[len(nums)//2]

時間計算量は、空間計算量は上記のように与えられたリストに対して破壊的な処理が許されているならです。

解法3

今回の問題に対して計算量の点で最も優れているのが、Boyer-Moore Voting Algorithmです。
数学的な証明がぱっとは分からないんですが、こんなアルゴリズムがあるのかと感心しました。

これは「投票結果から過半数の票を獲得した候補者がいるのであれば、それは誰か」という判定を効率的に行うアルゴリズムです。
変数が2つ、線形時間で計算も済む、という優れものです。

変数candidateで、過半数を獲得する可能性のある値を記憶します。
一方で変数countをカウンタとして用意します。candidateが現れたら+1、candidate以外が現れたら-1します。

値のリストを順に処理していき、countが0になったらそのcandidateが過半数を占めることはないと（一旦）考えて忘れ、次の値を新たなcandidateとして記憶します。
「一旦」と書いているのは、後でその値が再登場する可能性があるからですが、とにかく一旦忘れることとします。
すると、過半数を占める値が存在すれば、最後に残ったcandidateが過半数を占める値になっています。
もし過半数を占める値が存在しなければ、最後に残ったcandidateは必ずしも最も多く出現した値ではない点が、要注意であり面白いポイントです。

具体的な動作は以下の通りです。リストの各要素を処理したときの(candidate, count)をリスト右に示します。

Input: [2,2,1,1,1,2,2]

[2,2,1,1,1,2,2] (2,1)

[2,2,1,1,1,2,2] (2,2)

[2,2,1,1,1,2,2] (2,1)

[2,2,1,1,1,2,2] (1,1)

[2,2,1,1,1,2,2] (1,2)

[2,2,1,1,1,2,2] (1,1)

[2,2,1,1,1,2,2] (2,1)

Output: 2

面白いアルゴリズムですが、最大の難点は過半数を占める値があることが前提になっている点で、現実にはそこが保証されているケースはほとんどないので、日の目を見ることは少ないかもしれません。
ブロックチェーンが51%アタックを食らったときに攻撃者を特定する、とか・・・？

実装は以下のようになります。

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

時間計算量は、空間計算量はです。