Pythonで多数決により過半数の票を獲得した候補者のIDを見つける方法

本記事では、Pythonを使って多数決(過半数)を獲得した候補者のIDを見つけるプログラムを解説します。

問題の概要

n個の値を含む数値リスト nums があるとします。各数値は候補者への1票を表しています。この中から、floor(n/2) より多くの票を獲得した候補者のIDを見つけます。もし過半数の票を獲得した候補者が存在しない場合は、-1 を返します。

例えば、入力が nums = [6, 6, 2, 2, 3, 3, 3, 3, 3] の場合を考えてみましょう。リストの長さは9なので、過半数となるには5票以上が必要です。数値「3」は5回出現しているため、出力は 3 となります。

解決の手順

• l := リスト nums のサイズ(要素数)を取得します。
• count := 各数値とその出現回数を格納したマップ(Counter を使用)を作成します。
• count 内の各数値 i と出現回数 j について、以下の処理を繰り返します。
  • j > (l // 2)(出現回数が要素数の半分より多い)であれば、i を返します。
• 該当する候補者が見つからなければ、-1 を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, nums):
        l = len(nums)
        from collections import Counter
        count = Counter(nums)
        for i, j in count.items():
            if j > (l // 2):
                return i
        return -1

ob = Solution()
nums = [6, 6, 2, 2, 3, 3, 3, 3, 3]
print(ob.solve(nums))

入力

[6, 6, 2, 2, 3, 3, 3, 3, 3]

出力

3

コードのポイント

このソリューションの鍵となるのは、Python標準ライブラリの collections.Counter です。Counterはリスト内の各要素の出現回数を自動的に集計してくれるため、手動でカウント処理を実装する必要がなく、コードが非常にシンプルになります。

計算量についても確認しておきましょう。Counterによる集計はO(n)、その後の出現回数チェックのループも最大でO(n)程度であるため、アルゴリズム全体としてO(n)の時間計算量で動作し、大規模なデータに対しても効率的に処理できます。

また、過半数の候補者が存在しないケース(例:[1, 2, 3] のように全ての票が分散している場合)でも、ループが完了した時点で -1 が正しく返される点にも注目してください。