1. はじめに
この記事では、LeetCode の 169. Majority Element を解く。この問題の概要は次の通り。
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
配列のサイズを $n$ としたとき、$\dfrac{n}{2}$ 回より多く出現する要素を求める問題である。
2. 単純な解法
単純な解法の一つとして、連想配列を使う方法がある。連想配列を使って、要素の登場回数を調べる。そのあと、その中で最も多く出現した要素を返せばよい。
Python による実装を次に示す。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
hashSet = {}
for num in nums:
hashSet[num] = hashSet.get(num, 0) + 1
max_val = max(hashSet.values())
for key, value in hashSet.items():
if max_val == value:
return key
3. Boyer–Moore多数決アルゴリズム
ハッシュマップを使った方法の問題点として、空間計算量の大きさ（$= O(N)$）にある。
これを解決する手法として、Boyer–Moore Majority Vote Algorithm（ボイヤー＝ムーア多数決アルゴリズム）である。
このアルゴリズムの特徴は次の通り。
- 時間計算量：$O(N)$
- 空間計算量：$O(1)$
3.1. アルゴリズムの考え方
多数派の要素（過半数を占める要素）は、ほかの全ての要素とペアを組んで打ち消していっても、最終的に必ず残るという性質を利用する。
配列の各要素を順番に見ながら、次のように操作を行う。
- まず候補となる要素（$=$
res）と、その候補の得票数を表す要素（$=$cur）を用意する - もし、
curが 0 であれば、現在見ている要素を新しい候補として設定する - 要素が候補と一致する場合は
curを 1 増やし、異なる場合は 1 を減らす - 最後まで操作した時に残った候補
resが、配列中で過半数を占める要素となる
この打消しの過程を通して、多数派だけが最終的に残る。たとえば、$nums = [2, 1, 2, 1, 1, 2, 2]$ の場合、途中で候補が切り替わっても、最終的に 2 が残る。これが答えとなる。
3.2. 実装
Python による実装を次に示す。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
res = 0
cur = 0
for num in nums:
if cur == 0:
res = num
if res == num:
cur += 1
elif res != num:
cur -= 1
return res
この手法は単純でありながら、空間計算量を $O(1)$ を抑え、1回の操作（$= O(N)$）で解を求めることができる。したがって、ハッシュマップを用いる方法と比較してメモリ効率が良い。
4. まとめ
Boyer–Moore多数決アルゴリズムは、入力配列を1回走査するだけで、空間計算量 $O(1)$ のまま多数派要素を求めることができる極めて効率的な手法である。
| 手法 | 時間計算量 | 空間計算量 |
|---|---|---|
| ハッシュマップ法 | $O(N)$ | $O(N)$ |
| Boyer-Moore 法 | $O(N)$ | $O(1)$ |