LeetCode_287_FindtheDuplicateNumber

題目分析：

利用數(shù)組內(nèi)值都在下標(biāo)范圍內(nèi)的特點(diǎn)驰凛，數(shù)組可以有很多神奇操作稍浆，
第二種解法更是妙不可言刁赖。

解法一：

/**
 * 二分法:判斷在這區(qū)間內(nèi)的數(shù)的個(gè)數(shù)是否大于這份區(qū)間本身
 * 如果大于則一定有重復(fù)--- 鴿巢原理
 * [1, 4, 4, 2, 4]這種情況少3的情況也不必?fù)?dān)心 因?yàn)閰^(qū)間內(nèi)每少一個(gè)不重復(fù)數(shù) 必然多一個(gè)重復(fù)數(shù)
 */
public static int findDuplicate(int[] nums) {
    return find(1, nums.length - 1, nums);
}

public static int find(int begin, int end, int[] nums) {
    if(begin == end)
        return begin;

    int count = 0;
    int mid = (end + begin) / 2;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] >= begin && nums[i] <= mid)
            count++;
    }

    boolean inLeft = count > mid - begin + 1;

    if (inLeft) {
        return find(begin, mid, nums);
    } else
        return find(mid + 1, end, nums);
}

解法二：

/**
 * 若能證明：根據(jù)題意存在任意一組滿足要求的數(shù),可分為重復(fù)和非重復(fù)數(shù)兩類，
 * 一定存在一個(gè)按從nums[0]開始 善镰，step = nums[step]的步驟循環(huán)嵌套執(zhí)行形成的帶環(huán)鏈表跟衅，
 * 且入環(huán)口的值(某個(gè)nums[step])，一定是重復(fù)數(shù)的值石窑。
 * 則可按成環(huán)鏈表求入環(huán)口的方式操作牌芋，處理本題。
 *
 * 拆分為兩步的等效證明:
 * 證明1:從nums[0]開始,一定會(huì)走到nums[step]是重復(fù)數(shù)的一步
 * 證明2:nums[step]是重復(fù)數(shù)的情況松逊，那么nums[steps]之后成環(huán)躺屁，且是鏈表環(huán)入口
 *
 * 若能完成證明1，2 -- 即可完成證明棺棵。
 *
 * 引理1:若nums[step]是非重復(fù)數(shù)楼咳，一定會(huì)走到nums[step]是重復(fù)數(shù)
 *
 * 引理1證明:
 * 先假設(shè)我們能永遠(yuǎn)不走到nums[step]是重復(fù)數(shù)，那執(zhí)行過程中必然在非重復(fù)數(shù)之間成環(huán)烛恤，只需證明費(fèi)非復(fù)數(shù)無法成環(huán)即可母怜。
 * 假設(shè)能成環(huán)，入環(huán)口為某個(gè)非重復(fù)數(shù)缚柏，自然其位置是step_temp,值是nums[step_temp]苹熏，
 * 若要再次回到這個(gè)位置，必須是某另一個(gè)step等于step_temp,
 * (或者nums[step_temp] == step_temp,但這種情況最初就無法到達(dá)step_temp币喧，比如數(shù)值1在[1]位置上轨域，1不重復(fù)，怎么都到不了)杀餐，
 * 由于不重復(fù)干发，所有永遠(yuǎn)無法回到該入環(huán)口，無法成環(huán)史翘。
 * 由于無法在非重復(fù)數(shù)位置間成環(huán)枉长，則必將走到非重復(fù)數(shù)以外的位置，而其他所有位置都是重復(fù)數(shù)琼讽，固一定會(huì)走到nums[step]是重復(fù)數(shù)必峰。
 * 證畢
 *
 * 證明1:
 * 由于一開始從nums[0]開始
 * 如果nums[0]本身是重復(fù)數(shù)，則直接達(dá)成nums[step]是重復(fù)數(shù) -- 達(dá)成
 * 如果nums[0]本身是非重復(fù)數(shù)钻蹬，由引理1證明吼蚁，將走到nums[step]是重復(fù)數(shù) -- 達(dá)成
 * 證畢。
 *
 * 證明2:
 * 若nums[step]下一步也是重復(fù)數(shù)问欠，nums[steps]之后成環(huán)肝匆，且是鏈表環(huán)入口 -- 達(dá)成
 * 若nums[step]下一步是非重復(fù)數(shù)粒蜈，則由于引理論1，一定會(huì)走到nums[step]是重復(fù)數(shù)术唬，nums[steps]之后成環(huán)薪伏，且是鏈表環(huán)入口 -- 達(dá)成
 * 證畢
 *
 *
 */
public static int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }while (slow != fast);

    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
}