【Python】多数決でn/3を超える票を獲得した候補者を抽出するプログラム

問題概要

数値のリスト nums が与えられ、各数値はある候補者に対する1票を表しているとします。この中から、全投票数 n の3分の1（n / 3 の小数点以下切り捨て）より多くの票を獲得した候補者のIDを、昇順で求める必要があります。

例えば、入力が nums = [3, 2, 6, 6, 6, 6, 7, 7, 7, 7, 7] の場合、出力は [6, 7] になります。これは、候補者6と候補者7がそれぞれ全投票の約40%を獲得しており、基準となる33%を上回っているためです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 結果を格納するための空の集合 ans を用意する
• リスト nums を昇順にソートする
• インデックス i を0で初期化し、n にリストのサイズを代入する
• i がリストのサイズ未満である間、以下を繰り返す
  • nums[i] の出現回数が n // 3 を超えていれば、その値を ans に追加する
  • i を n // 3 ずつ進める
• ans をソートして返す

ここでのポイントは、リストを事前にソートしておくことで同じ値が連続して並ぶようになる点です。そのため、n // 3 間隔で要素をサンプリングすれば、出現回数が n / 3 を超える値を必ず捉えることができます。

実装例

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

class Solution:
    def solve(self, nums):
        ans = set([])
        nums.sort()
        i = 0
        n = len(nums)
        while i < len(nums):
            if nums.count(nums[i]) > n // 3:
                ans.add(nums[i])
            i += n // 3
        return sorted(list(ans))

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

入力

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

出力

[6, 7]

計算量と注意点

ソートに O(n log n) のコストがかかりますが、ループ内の count() 呼び出しは n // 3 間隔で進むため最大でも3回程度しか発生せず、全体の計算量は O(n log n) に抑えられます。

また、数学的な性質として、出現回数が n / 3 を超える要素は最大でも2種類しか存在しないため、答えの候補者数は高々2人です。

なお、リストの長さが3未満の場合は n // 3 が0となり無限ループに陥る可能性があるため、実運用ではそのケースに対するガード処理を加えておくと安全です。