はじめに
LeetCodeで出題された内容から、調べたことを自分用の備忘録として残しています。
多数派要素とは
全体の要素の半数以上（つまり、全体の要素数の半分を超える）登場する要素
具体例：
リスト: [3, 2, 3]
このリストには3つの要素があり、それぞれの登場回数は次の通りです。
- 3 が2回登場
- 2 が1回登場
この場合、リストに含まれる要素の数が3つなので、その半数は 3 ÷ 2 = 1.5 です。これを切り上げた数の 2回以上登場する要素が多数派要素です。この場合、3 が2回登場しているため、3 が多数派要素になります。
多数派要素の取得アルゴリズム
今回は、以下の３つの方法について、ご紹介します。
1. ボイヤー・ムーアの多数決アルゴリズムを使う方法
私が最初に実装したのが、この方法です。
ネット検索でヒットしたものから引用しましたが、よくできたアルゴリズムだなぁと思います。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
if num == candidate:
count += 1
else:
count -=1
return candidate
時間計算量：O(n)
配列を1回だけ走査するため。
追記： 多数派要素が存在しない場合を考慮した実装
上記のコードは、多数派要素が存在しない場合が考慮されていないので、以下の処理を追記しました。
ご指摘ありがとうございました。
- 候補が本当に多数派要素かどうかを確認する処理
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = None
count = 0
# 1. ボイヤー・ムーア多数決アルゴリズムで多数派候補を見つける
for num in nums:
if count == 0:
candidate = num
if num == candidate:
count += 1
else:
count -= 1
# 2. 候補が本当に多数派要素かを確認する
count = 0
for num in nums:
if num == candidate:
count += 1
# リストの半数を超えているか確認
if count > len(nums) // 2:
return candidate
else:
# 多数派要素が存在しない場合、その旨のメッセージを返す
return "多数派要素は見つかりませんでした"
時間計算量: O(n)
配列を2回走査するため。
2. Pythonのcollections.Counterクラスを使った方法
collections.Counterクラスと組み込み関数maxを使うとより簡潔なコードが書けます。
時間計算量は、多数決アルゴリズムと変わりません。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
a=Counter(nums)
return max(a, key=a.get)
時間計算量：O(n)
collections.Counterの計算量、maxの計算量ともにO(n)のため。
参考サイト：
https://qiita.com/ell/items/259388b511e24625c0d7
https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb
ドキュメント：
https://docs.python.org/ja/3/library/collections.html#collections.Counter
https://docs.python.org/ja/3/library/functions.html#max
3. 昇順にソートして中央値の要素を返す
簡潔なコードで書ける上に、先の２つの方法と比較して速く処理ができます
処理速度は遅くなります。（実行環境等により異なる場合があります）
それでも、スマートな方法と感動しました！
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]
時間計算量：O(n log n)（n はリストの要素数）
- nums.sort() の計算量:
sort() は内部的に「Timsort」というアルゴリズムを使用しており、平均・最悪の場合でも O(n log n) です。ここで、n は nums の要素数です。 - nums[len(nums) // 2] の計算量:
リストの中央の要素にアクセスする操作は定数時間（O(1)）で行えます。
最後まで読んでくださって、ありがとうございます。誤り等あれば、ご指摘くださるとありがたいです。
※ 時間計算量の比較について、記載誤りがありました。ご指摘ありがとうございました！
また、今回紹介した方法の２と３も、多数決アルゴリズムと同様、多数派要素が存在することを前提とした効率的な実装方法として記載しております。