每日修仙嘗試于9102年7/8.希望本座早日習得九陽神功，便可在靈石之路上助爾等一臂之力。

如題：

• 給定一個包含 n + 1 個整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數(shù)。假設只有一個重復的整數(shù)，找出這個重復的數(shù)。

示例：
輸入：{1,4,5,9,10,2,3,7,8,6,9}
輸出：9

說明：
1、不能更改原數(shù)組（假設數(shù)組是只讀的）。
2、只能使用額外的 O(1) 的空間。
3、時間復雜度小于 O(n2) 。
4、數(shù)組中只有一個重復的數(shù)字，但它可能不止重復出現(xiàn)一次。

解法一：

使用Set，這個就不用多BB了。但是一般使用這種解法，是不會有加分的，也就是說，你的面試者可能不會認可你。So，你可能要了解一哈“鴿子洞原理”（也稱之為“抽屜原理”）了。

解法二：

弗洛伊德的烏龜和兔子（循環(huán)檢測）。對于每對索引 i 和值 v_i而言，“下一個” v_j 位于索引 v_i處，我們可以將此問題減少到循環(huán)檢測。

public class TortoiseAndHare {
    
    public static void main(String[] args) {
        int nums[] = {1,4,5,9,10,2,3,7,8,6,9};
        int dup = findDuplicate(nums);
        System.out.println(dup);
    }
    /**
     * 弗洛伊德的烏龜和兔子
    
     * <p>Title: findDuplicate</p>  
    
     * <p>Description:因為 nums 中的每個數(shù)字都在 1 和  n 之間，所以它必須指向存在的索引。此外，由于 0不能作為 nums 中的值出現(xiàn)，
     nums[0] 不能作為循環(huán)的一部分 </p>  
    
     * @return
     */
    public static int findDuplicate(int nums[]) {
        int i = 0;
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
            System.out.print("第{"+(++i)+"}次");
            System.out.print(" tortoise="+tortoise);
            System.out.println(" hare="+hare);
        }while(tortoise != hare);
        
        return tortoise;
        
    }
    

執(zhí)行結果如下：

第{1}次 tortoise=4 hare=10
第{2}次 tortoise=10 hare=6
第{3}次 tortoise=9 hare=9
9

天地三清，道法無常。
溜溜球...