Pythonで配列内の重複する数値を検出する方法（フロイドの循環検出アルゴリズム）

n + 1 個の整数を含む配列 nums があるとします。各要素は 1 から n の範囲に収まっており、鳩の巣原理により、少なくとも1つの重複した数値が必ず存在することが証明できます。ここでは重複している数値が1つだけであると仮定し、その重複要素を見つけることが課題となります。例えば、配列が [1,3,4,2,2] の場合、重複要素は 2 です。

解決のための手順

この問題は、フロイドの循環検出法（ウサギとカメのアルゴリズム）を応用することで、追加メモリ O(1) で効率的に解けます。手順は以下の通りです。

• a := nums[0]、b := nums[0] として初期化する
• 無限ループを実行する
  • a := nums[nums[a]]（2ステップ進む）
  • b := nums[b]（1ステップ進む）
  • a = b になったらループを抜ける
• ptr := nums[0] として初期化する
• ptr が b と等しくなるまで以下を繰り返す
  • ptr := nums[ptr]
  • b := nums[b]
• ptr を返す

配列の各値を「次のインデックスへのポインタ」とみなすと、この配列は必ず循環するリンク構造になります。そして、重複する数値こそがその循環（サイクル）の入り口に相当するため、サイクルの始点を検出することで重複数値を特定できるのです。

実装例

より理解を深めるために、以下のPythonコードをご覧ください。

class Solution(object):
   def findDuplicate(self, nums):
      hare = nums[0]
      tortoise = nums[0]
      while True:
         hare = nums[nums[hare]]
         tortoise = nums[tortoise]
         if hare == tortoise:
            break
      ptr = nums[0]
      while ptr!=tortoise:
         ptr = nums[ptr]
         tortoise = nums[tortoise]
      return ptr
ob1 = Solution()
print(ob1.findDuplicate([3,1,3,4,2]))

入力

[3,1,3,4,2]

出力

3

このアルゴリズムの計算量は O(n)、追加のメモリ使用量は O(1) であり、元の配列を変更することなく定数空間で重複を検出できるのが大きな特徴です。