My code:

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0)
            return -1;
        int begin = 1;
        int end = nums.length;
        while (begin < end) {
            int mid = begin + (end - begin) / 2;
            int counter = 0;
            for (int i = 0; i < nums.length; i++)
                if (nums[i] <= mid)
                    counter++;
            if (counter > mid)
                end = mid;
            else
                begin = mid + 1;
        }
        return begin;
    }
}

這道題目我沒能想出來。感覺有點考智商。那個想法我的確沒想出來。
首先貼一個博文。
http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/

然后這道題目有O(n) 的做法。但是感覺思路太復(fù)雜了。就忽略了。
然后思考了下他的第二種做法， O(n log n)
舉個例子：
假設(shè)n = 9
那么，有10個位置放入1-9
肯定會有重復(fù)。
取中間值 1 + (10 - 1) / 2 = 5;
在1-9中， <= 5 的應(yīng)該有5個，假設(shè)不重復(fù)。
但是如果1-5之間有數(shù)字重復(fù)了，那么，就應(yīng)該大于5個了。
所以，遍歷下整個數(shù)組，統(tǒng)計 <=5 的個數(shù)，如果大于5，那么就表示，
那個重復(fù)的數(shù)字，他的值v ， 1 <= v <= 5
也就是
begin <= v <= mid
反之，則是：
mid + 1 <= v <= end
于是采用binary search 的思想，一步步往下縮小范圍。最終，就能把v限定在一個確定值里面，此時，
begin = end
所以，最終可以找到這個值。

**
總結(jié)： 不在是binary search array, 而是 通過 binary search 來限定一個可能性取值的范圍。最終達到目的。
**

Anyway, Good luck, Richardo!

My cdoe:

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0)
            return -1;
        int begin = 1;
        int end = nums.length -1; // end = n
        while (begin < end) {
            int target = (begin + end) / 2;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] >= begin && nums[i] <= target)
                    count++;
            }
            if (count > target - begin + 1) {
                end = target;
            }
            else {
                begin = target + 1;
            }
        }
        return begin;
    }
}

寒假在家效率實在太低。這道題目再做也還是沒有做出來。shit
思路還是聽巧妙地。
Anyway, Good luck, Richardo!

My code:

public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int i = 0;
        while (i < nums.length) {
            if (nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
            else if (nums[i] - 1 == i) {
                i++;
                continue;
            }
            else {
                return nums[i];
            }
        }
        
        return -1;
    }
}

這道題目的思想和
http://www.itdecent.cn/p/fc874688359e
差不多。

然后看了下以前的做法，也是真的巧妙啊。感覺復(fù)雜度也是O(n)啊 ？

Anyway, Good luck, Richardo! -- 09/01/2016

最新的做法不太對。因為我修改了原數(shù)組。這是不允許的。
所以一開始的做法才是正確的。

Anyway, Good luck, Richardo! -- 09/11/2016