# LeetCode Medium 287. Find the Duplicate Number

tags: leetcode

問題

• Explore
• Problems

アイデア

要素数がn + 1の整数の配列が与えられた時，要素は[1, n]であり，鳩の巣原理より少なくとも1つの要素は重複しています．

このうち，重複している要素を探せというもの．

注意点は

• 配列を操作してはいけない．
  • つまりstd::sortは使えない．
• 空間計算量は$O(1)$しか許されていない．
  • つまり新たなデータ構造が使えない．
• 時間計算量は$O(n^{2})$よりも小さい必要がある．
  • つまり2重ループも使えない．
• 1つしか重複した数はないが，それは1つ以上重複している可能性がある．

解法

この問題ではcycle detectionを行うと空間計算量が$O(1)$で済みます．

配列の要素は[1, n]です．つまり，これらの要素は必ずある要素の添字となります．つまり，ある要素を添え字とする配列の要素から，その要素を添え字とする要素と飛ぶとすると[1, n]の添字内で循環が発生します．

また，0は要素として現れないのでnums[0]は循環の一部とはなりえません．つまり，この問題は循環がどこで生じているのかを見つければ良いのです．

つまり，func(index) = elementとなるような写像関係を考えれば良いです．例えば

• [1,3,4,2,2]
  • 0 -> 1, 1 -> 3, 2 -> 4, {3, 4} -> 2
  • という写像関係があります．このとき，
  • 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> 2 ->...となり途中から2, 4が連続します．このような数列の最初の数が今回求めるものです．

これからすることを図示すると以下のようになります．

• ループの開始点に行くまでにxステップ必要で，ループ内で両者が会う場所は開始点からyステップ必要で，両者が会った場所からループの開始点まではzステップ必要とします．
• 最初のループでは1ステップごと進む要素(tortoise)と2ステップごと進む要素(hare)を使って，ステップ内に片方の要素を入れます．
  • このときにtortoiseはx+y動きます．
  • また，hareはx+2y+z動きます．
  • ここから，hareはtortoiseの2倍のステップ動くので2(x+y)=x+2y+z，つまりx=zとなります．
• 2つ目のループでは上の結果を利用します．
  • 上よりx=zであり，tortoiseを初期値に戻し，既にmeeting pointにいるhare一緒に1ステップずつ動かします．
  • そうするとループの開始点で両者は会うことができ，これが求める答えです．

計算量

配列の長さは$N$として

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int findDuplicate(vector<int>& nums) {
    if (nums.size() <= 1)
      return -1;
    
    int tortoise = nums[0];
    int hare = nums[nums[0]];
    while (tortoise != hare) {
      tortoise = nums[tortoise];
      hare = nums[nums[hare]];
    }
    
    hare = 0;
    while (hare != tortoise) {
      hare = nums[hare];
      tortoise = nums[tortoise];
    }
    return hare;
  }
};