Pythonでソート済み配列から重複要素を削除する方法

ここでは、ソート済みのリストから重複する要素をすべて削除し、その後の配列の長さ（ユニークな要素の個数）を返す問題を扱います。

重要な制約として、O(1)の追加メモリで実行する必要があります。つまり、新しい配列を作成せずに、元の配列をインプレース（in-place）で操作しなければなりません。

問題の例

例えば、次のような入力が与えられたとします。

A = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]

この場合、重複を除いたユニークな要素は「1, 2, 3, 4, 5, 6」の6つなので、出力は 6 となります。

解法のアプローチ

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

• リストが空の場合は、0 を返す
• それ以外の場合は、まず prev をリストの最初の要素とし、カウンタ length を初期化する
• i を 1 から n-1 までループさせる
  • A[i] が prev と異なる場合：
    • length を 1 増やす
    • prev を A[i] に更新する
• 最後に length を返す

このアルゴリズムは二つのポインタ（インデックス）を使うテクニックに基づいています。一つは現在走査中の位置を追跡し、もう一つはユニークな要素を書き込む位置を管理します。配列がすでにソートされているため、隣接する要素同士を比較するだけで重複を検出できるのがポイントです。

Pythonでの実装例

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

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        length = 1
        previous = nums[0]
        index = 1
        for i in range(1, len(nums)):
            if nums[i] != previous:
                length += 1
                previous = nums[i]
                nums[index] = nums[i]
                index += 1
        return length

input_list = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]
ob1 = Solution()
print(ob1.removeDuplicates(input_list))

入力

[1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]

出力

6

計算量について

• 時間計算量： O(n) — 配列を一度だけ走査すればよいため、要素数 n に対して線形時間で処理が完了します。
• 空間計算量： O(1) — 追加の配列やデータ構造を使用せず、定数個の変数だけで処理できるため、メモリ効率に優れています。

この手法は、LeetCodeなどのコーディング面接でも頻出の「Remove Duplicates from Sorted Array」問題の標準的な解法です。ソート済みという前提条件があるからこそ、シンプルな隣接比較だけで重複削除が実現できる点を押さえておきましょう。