【Python】リスト内の重複要素を見つけて最後の出現箇所だけを削除する方法

数値のリストが与えられたとき、その中から重複している数値をすべて見つけ出し、最後に出現した箇所のみを削除するプログラムを考えます。

例えば、入力が [10, 30, 40, 10, 30, 50] の場合、10 と 30 がそれぞれ2回ずつ出現しています。これらの最後の出現箇所を取り除くと、出力は [10, 30, 40, 50] になります。

解決のための手順

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

• seen := 新しい辞書（マップ）を作成する
• d := 新しい辞書（マップ）を作成する
• i を 0 から nums のサイズまで繰り返す：
  • nums[i] が d に存在しない場合は d[nums[i]] := 1 とする
  • 存在する場合は d[nums[i]] := d[nums[i]] + 1 とする
• i := 0 とし、i が nums のサイズ未満である間、以下を繰り返す：
  • n := d[nums[i]] とする
  • nums[i] が seen に存在しない場合は seen[nums[i]] := 1、存在する場合は seen[nums[i]] := seen[nums[i]] + 1 とする
  • n が seen[nums[i]] と等しく、かつ n > 1 の場合（＝現在の要素が最後の出現であり、かつ重複している場合）、nums の i 番目の要素を削除する
  • i := i + 1 とする
• nums を返す

実装例

理解を深めるために、以下の実装例を見てみましょう。

class Solution:
    def solve(self, nums):
        seen={}
        d={}
        for i in range(len(nums)):
            if not nums[i] in d:
                d[nums[i]]=1
            else:
                d[nums[i]]+=1
        i=0
        while i < len(nums):
            n=d[nums[i]]
            if not nums[i] in seen:
                seen[nums[i]]=1
            else:
                seen[nums[i]]+=1
            if n == seen[nums[i]] and n > 1:
                nums.pop(i)
            i-=1
            i+=1
        return nums

ob = Solution()
print(ob.solve([10, 30, 40, 10, 30, 50]))

入力

[10, 30, 40, 10, 30, 50]

出力

[10, 30, 40, 50]

アルゴリズムのポイント

このアルゴリズムの鍵は、事前に各要素の総出現回数を計算しておくことです。最初のループで辞書 d に各数値の出現回数を記録し、2周目の走査では辞書 seen を使って「その要素が何回目の出現か」を追跡します。記録した回数が総出現回数と一致した時点で、その要素が最後の出現であると判断でき、さらに出現回数が2以上（＝本当に重複している）の場合にのみ削除を行うことで、初回の出現を残しつつ最後の出現だけを取り除けます。

また、pop() で要素を削除すると後続の要素が前に詰められ、位置関係がずれる点にも注意が必要です。このコードでは削除時にインデックスを進めないよう調整することで、リストの長さが変化しても正しく走査を続けられるようにしています。