Pythonで1からnの範囲のn+1個の数値から重複する要素を見つける方法

Pythonで1からnの範囲のn+1個の数値から重複する要素を見つける方法

長さ n+1 の数値リスト nums があるとします。これらの数値はすべて 1, 2, ..., n の範囲から選ばれています。鳩の巣原理(ピジョンホール原理)により、このリストには必ず重複が存在することが分かります。この重複する要素を見つけて返すのが、この問題の目的です。

例えば、入力が [2, 1, 4, 3, 3] の場合、出力は 3 となります。

解法のアプローチ

この問題は、合計値の差を利用することで効率的に解くことができます。手順は以下の通りです。

• l := nums のサイズ(n+1 に相当)
• temp := l * (l - 1) / 2(1 から n までの理論上の合計値)
• temp_sum := nums の全要素の合計
• temp_sum - temp を返す(これが重複値)

この方法が機能する理由は、1 から n までの連続する整数の合計が n(n+1)/2 で計算できるためです。リストの長さ l は n+1 なので、l(l-1)/2 は 1 から n までの理論上の合計値と一致します。実際の合計値からこの理論値を引けば、余分に含まれている重複した数値が求まります。

このアルゴリズムの計算量は時間 O(n)、空間 O(1) であり、非常に効率的です。

実装例

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

class Solution:
   def solve(self, nums):
      l = len(nums)
      temp = l*(l-1)/2
      temp_sum = sum(nums)
      return temp_sum-temp
ob = Solution()
print(ob.solve([2, 1, 4, 3, 3]))

入力

[2, 1, 4, 3, 3]

出力

3

このように、数学的な性質を活かすことで、ソートやハッシュセットを使わずに重複検出を O(n) 時間で実現できます。