Pythonでリスト内の最大の一意の数を求める方法

数値のリストが与えられたとき、その中で一度だけ出現する要素のうち最大のものを返す問題を考えてみましょう。該当する要素が存在しない場合は -1 を返します。例えば、リストが [5,2,3,6,5,2,9,6,3] の場合、9 は一度しか現れないため、出力は 9 となります。

解決のアプローチ

この問題は、辞書(ハッシュマップ)を使うことで効率的に解くことができます。手順は以下の通りです。

• 各要素を順番に確認し、辞書に格納します。要素がまだ辞書に存在しない場合は新しいエントリを作成し、すでに存在する場合はカウント値を1つ増やします。
• 次に辞書全体を走査し、カウントが 1 になっているキー(= 一度だけ出現した要素)の中から最大のものを返します。

Pythonでの実装例

以下のコードを見て、具体的な動作を理解しましょう。

class Solution(object):
    def largestUniqueNumber(self, A):
        d = {}
        ans = -1
        for i in A:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        for a, b in d.items():
            if b == 1:
                ans = max(a, ans)
        return ans

ob1 = Solution()
print(ob1.largestUniqueNumber([5,2,3,6,5,2,9,6,3]))

入力

[5,2,3,6,5,2,9,6,3]

出力

9

計算量について

このアルゴリズムの時間計算量は O(n) です(n はリストの長さ)。各要素を一度ずつ走査してカウントし、その後辞書のエントリを確認するだけで済むためです。空間計算量も O(n) となり、要素の出現回数を記録するための辞書が必要になります。

なお、Pythonでは collections.Counter を使えば、カウント処理をさらに簡潔に書くことも可能です。