Pythonでソート済みリストから一意な整数の個数を求める方法

ソートされた数値リスト nums が与えられたとき、そのリストに含まれる一意な要素（重複を除いた値）の個数を求める問題について解説します。

例えば、入力が nums = [3, 3, 3, 4, 5, 7, 7] の場合、一意な数値は [3, 4, 5, 7] となるため、出力は 4 になります。

解決のアプローチ

この問題は、セット（集合）を使うことでシンプルに解決できます。手順は以下の通りです。

• 空のセット s とカウンター cnt = 0 を用意する
• nums の各要素 i について以下を繰り返す
  • i がまだセット s に存在しない場合、i をセットに追加し、cnt を1増やす
• 最後に cnt を返す

実装例

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

class Solution:
    def solve(self, nums):
        s = set()
        cnt = 0
        for i in nums:
            if i not in s:
                s.add(i)
                cnt += 1
        return cnt

ob = Solution()
print(ob.solve([3, 3, 3, 4, 5, 7, 7]))

入力

[3, 3, 3, 4, 5, 7, 7]

出力

4

より簡潔な書き方

Pythonでは、セットの特性を活かせば、この処理を1行で表現することもできます。

def solve(nums):
    return len(set(nums))

print(solve([3, 3, 3, 4, 5, 7, 7]))  # 出力: 4

set(nums) でリストから重複が自動的に除去され、len() でその要素数を取得できます。コードも読みやすく、実務でも推奨される書き方です。

計算量について

どちらの方法でも、各要素に対してセットへの挿入・検索を行うため、時間計算量は O(n)、空間計算量もセットに最大 n 個の要素を格納するため O(n) となります。リストがソート済みであることを利用すれば、隣接する要素同士を比較する方法（O(1) の追加メモリ）もありますが、セットを使う方法が最も直感的で汎用的です。