[287] Find the Duplicate Number

還以為要用XOR, 結果不用XD
一整個想太多XDDDDDD
但是不能更改輸入的array,
又要求只能有O(1)的extra space
感覺很難！（就說是hard了啊XD)

先來個暴力法
Find the Duplicate Number
int findDuplicate(int* nums, int numsSize) {
    int i,j;
    for (i=0;i< numsSize-1;i++)
        for (j=i+1;j<numsSize;j++)
            if (nums[i] == nums[j])
               return nums[i];
    return -1;
}

想當然時間很慢.
看了討論原來這是有名的龜兔賽跑演算法 ! （Tortoise and Hare Algorithm）
也叫做 Floyd’s cycle detection algorithm
證明太複雜了我也不確定我有沒有懂
用來找出一個linked list裡面有沒有cycle , cycle的長度, cycle的起點.
說是讓烏龜一次走一步, 兔子一次走兩步, 若走完整個linked list都沒有相遇,
表示裡面沒有環.
若有環, 它們走一走一定會在環裡面相遇.
相遇時, 假設烏龜走了 k 步, 兔子走了 2k 步,
這個k 一定是環的長度的整數倍, 若環的長度是 r , 也就是 k = nr
(因為兔子比烏龜多走了環的倍數步, 也就是 2k - k = k  可推知 k = nr )

難後呢！（已經昏）（昏的是我不是烏龜也不是兔子）（沒人誤會！）
龜兔重逢後讓兔子留在原地, 烏龜一次一步往前走, 下一次牠們再相遇,
這次烏龜走的步數就是環的長度. （這部分感覺容易理解！）

又然後, 建立在上面的推論, 設linked list的起點走到環的起點是 s 步,
再假設龜兔相遇的地方是環開始後的第 m 步,
我們剛剛說烏龜在k 處和兔子相遇,
所以 s + m = k = nr
這時讓烏龜（或兔子也可以 whatever）回到起點,
另一隻留在相遇處m
讓兩隻都同時前進, 一次前進一步,
這次兩隻相遇的地方就會是環的起點！！！（到底為什麼）
有一個說法是留在原地的因為是在環的裡面繞, 所以是 nr
回到起點的會再走 s + m 步 (感覺也是廢話) s+m = nr (這剛剛好像講過XD）
那跟牠們相遇的地方是不是環的起點到底有什麼關係XD (對啦我沒天份)
s+m = nr
s = nr -m
s = (n-1) r + r - m
然後呢！！！為什麼可以取n = 1 然後就變成 s = r - m ?! 囧
好吧放棄XD 反正證明就是這樣
感覺我應該寫在找 linked list cycle的地方
那我為什麼不呢 ？！ 因為我還沒寫它啊哈哈哈哈哈～～～～

更驚人的就是
為什麼找出重覆的數字, 會讓你聯想到龜兔賽跑演算法呢為什麼～～～～（搖想出來的人的肩膀）（各種抱怨）（結果寫到這裡肚子餓了, 弄個早餐先XD）

***吃完早餐分隔線吃完早餐分隔線***
結果雖然勉強搞懂linked list的 cycle,
套到這題: 找重覆數字 又覺得很奇怪XD
為什麼這裡的一步兩步, 不是指index的加一跟加二呢?!
而是指拿array 裡的數字出來當它的步數
這樣還是一步兩步嗎?!  （請說中文啊XD～～～～）
總之code 長這樣:
int findDuplicate(int* nums, int numsSize) {
    int one=nums[0];
    int two=nums[nums[0]];
    while (one != two)
    {
        one = nums[one];
        two = nums[nums[two]];
    }
    two = 0;
    while (one!=two)
    {
        one = nums[one];
        two = nums[two];
    }
    return one;
}
這意思就是說如果array長的是 {4,1,2,2,3}
那我的一步one 就是 nums[0] = 4
兩步two 是 nums[nums[0]] = 3
how come!!!!!!
這跟龜兔賽跑的一步兩步為什麼看起來一點關係都沒有！！！
是一個取總長的概念嗎！！！
演算法真是太難了（難的好像是數學）
我還是回家吃自己吧呵呵呵(煮過期泡麵ing)

聽說是一個移動距離會怎樣怎樣的概念
然後這是一個例子 : leetcode discusstion
但是用例子來看我還是不懂它們為什麼要這樣寫
啊..............(倒地)