多数派要素の取得　Python

はじめに

LeetCodeで出題された内容から、調べたことを自分用の備忘録として残しています。

多数派要素とは

全体の要素の半数以上（つまり、全体の要素数の半分を超える）登場する要素

具体例：

リスト: [3, 2, 3]
このリストには3つの要素があり、それぞれの登場回数は次の通りです。

• 3 が2回登場
• 2 が1回登場
  この場合、リストに含まれる要素の数が3つなので、その半数は 3 ÷ 2 = 1.5 です。これを切り上げた数の 2回以上登場する要素が多数派要素です。この場合、3 が2回登場しているため、3 が多数派要素になります。

多数派要素の取得アルゴリズム

ボイヤー・ムーアの多数決アルゴリズムを使う方法

私がまっさきに考えたのが、この方法です。

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回だけ走査するため。

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

昇順にソートして中央値の要素を返す

簡潔なコードで書ける上に、先の２つの方法よりも速く処理ができます。
スマートな方法と感動しました！

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)）で行えます。

最後まで読んでくださって、ありがとうございます。誤り等あれば、ご指摘くださるとありがたいです。